dijkstra鏈路
首先，引進(jìn)一個輔助向量d，它的每個分量d[i]表示當(dāng)前所找到的從始點v到每個終點vi的的長度：如d[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強(qiáng)調(diào)相對就是說在算法過程中d的值是在不斷逼近最終結(jié)果但在過程中不一定就等于長度。它的初始狀態(tài)為：若從v到vi有弧，則d為弧上的權(quán)值；否則置d為∞。顯然，長度為 d[j]=min{d | vi∈v} 的路徑就是從v出發(fā)的長度最短的一條。此路徑為(v,vj)。 那么，下一條長度次短的是哪一條呢？假設(shè)該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權(quán)值，或者是d[j]和從vj到vk的弧上的權(quán)值之和。 一般情況下，假設(shè)s為已求得的終點的集合，則可證明：下一條最短路徑（設(shè)其終點為x）或者是弧(v,x)，或者是中間只經(jīng)過s中的頂點而最后到達(dá)頂點x的路徑。因此，下一條長度次短的的長度必是d[j]=min{d | vi∈v-s} 其中，d或者是弧(v,vi)上的權(quán)值，或者是d[k](vk∈s)和弧(vk,vi)上的權(quán)值之和。算法描述如下： 1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞（在本程序中為maxcost）。s為已找到從v出發(fā)的的終點的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點vi可能達(dá)到的度的初值為d=arcs[locate vex(g,v),i] vi∈v 2）選擇vj，使得d[j]=min{d | vi∈v-s} 3）修改從v出發(fā)到集合v-s上任一頂點vk可達(dá)的最短路徑長度。