3.1 基于Dijkstra算法的路径分析
Dijkstra（迪杰斯特拉）算法是典型的最短路径路由算法，也是一种单源路径算法，用于计算一个节点到其他所有节点的最短路径。该算法的主要特点是以起始点为中心向外层扩展，知道扩展到终点为止，Dijkstra算法对处理非负权边的最短路径问题是比较高效的。Dijkstra算法方法简明，能得出最短路径的最优解，但由于它遍历计算的节点很多，所有效率低，同时运算时占用空间大。
3.1.1 应用示例：极地探险
3.1.2 基于Dijkstra的最短路径规划
Dijkstra算法时很有代表性的最短路径算法，其思想是，设置顶点集合S并不断地进行贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该点的最短路径长度已知。
初始时，S中仅含有源。设U是G的某一个顶点，把从源到U且中间只经过S中顶点的路称为从从源到U的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Diskstra算法每次从V-S中取出具有最短特殊路长度的顶点U，将U添加到S中，同时对数组dist进行必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。
网友评论