最短路径之Dijkstra算法

最短路径之Dijkstra算法2014-12-12Dijkstra算法：

首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度：如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为（v,vj）。那么，下一条长度次短的是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是（v,vk），或者是（v,vj,vk）。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。一般情况下，假设S为已求得的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧（v,x），或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧（v,vi）上的权值，或者是D[k]（vk∈S）和弧（vk,vi）上的权值之和。

算法描述如下：

1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的度的初值为D=arcs[Locate Vex（G,v）,i] vi∈V

2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。

考虑如下无向网（假设从v0出发）:

最短路径数组变化情况：

最初，v0能到达的点为v2,v4,v5,距离分别为10,30,100,到其余点的距离默认为无穷大（max）,

然后，取最小权10,纳入S集，即v2点。又v2可以到达v3，距离为50。则v0->v3的距离可为10+50=60,小于当前的值（max）,故更新辅助数组。紧接着，再取出一个最小权30（去掉之前的10）,即v4,又v4可以到达v3,v5,距离分别为20,60,则v0->v3,v0->v5的距离可以分别为30+20=50,30+60=90,小于目前的值60,100,故而继续更新辅助数组。以此类推，最终得到一个最短路径数组。