最短路径—Dijkstra算法

diggersun

Dijkstra算法(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，里面包含着很多算法思想，贪心，广搜，松弛等等，很值得学习。在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
若全部边权为正，当起点V出发的若干条边E1,E2,E3**En等边中，最短的是Ei，那么以后不再可能出现比Ei更短的路径了，因为边权为正，以后只会越加越多。我们，我们标记Ei对应的点Vk为vis=1，更新从Vk出发的所有边的路径长度，再找起点V出发的终点Vk的vis=0的所有边中的最小值，继续标记对应的点，松弛它出发的边的路径长度，直到我们需要的那个点被标记，最短路径找到。
一张图来说明这个过程

admin

这个dijkstra思想理解了之后我们就开始编程序，一段段的来，先

diggersun

以上面的图为例详细解释下，计算从a出发到所有点的最短路径，先设置dis(a)=0，其他的dis=inf。所有的vis=0找vis=0的点中最短的是dis(a)=0，不可能比0再更短，所以a被标记，这个显然。
a出发三条边，ab=24 ac=8 ad=15，最短是是ac=8。 所以以后不会再有比8更短的可能了，因为所有的边都是正，只会越加越大！
标记c的vis=1，c出发的两条边ce、cf，那么更新下他们的值，先前是inf，现在分别变成了ae=15、af=11。这个过程叫做松弛操作，一旦发现比先前小的路径，马上更新。很容易理解。
现在vis=0的点中ab=24 ad=15 ae=15 af=11 ag=inf，最小的af=11，同上，以后也不可能有比11更小的，标记f的vis=1，更新f的出边d和g  ad=11+5=16，比先前的ad=15大，不需要更新，ag=11+3=14,更新ag。
余此类推！