dijkstra链路
首先，引进一个辅助向量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可达的最短路径长度。