Dijkstra 算法原理及实现
1
Dijkstra 算法
1.
定义
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节
点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，
直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法，在很多
专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，
找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
2.
算法原理
1)算法思想：设 G=(V,E)是一个带权有向图，把图中顶点集合 V 分成两
组，第一组为已求出最短路径的顶点集合（用 S 表示，初始时 S 中只有一
个源点，以后每求得一条最短路径 , 就将加入到集合 S 中，直到全部顶点
都加入到 S 中，算法就结束了），第二组为其余未确定最短路径的顶点集合
（用 U 表示），按最短路径长度的递增次序依次把第二组的顶点加入 S 中。
在加入的过程中，总保持从源点 v 到 S 中各顶点的最短路径长度不大于从源
点 v 到 U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中
的顶点的距离就是从 v 到此顶点的最短路径长度，U 中的顶点的距离，是从
v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。
(1) 初始时，S 只包含起点 s；U 包含除 s 外的其他顶点，且 U 中顶点
的距离为"起点 s 到该顶点的距离"[例如，U 中顶点 v 的距离为(s,v)的长度，
然后 s 和 v 不相邻，则 v 的距离为∞]。
(2) 从 U 中选出"距离最短的顶点 k"，并将顶点 k 加入到 S 中；同时，
从 U 中移除顶点 k。
(3) 更新 U 中各个顶点到起点 s 的距离。之所以更新 U 中顶点的距离，
