最短路徑

對于網(wǎng)圖來說，最短路徑，是指兩頂點之間經(jīng)過的邊上權(quán)值之和最少的路徑，并且我們稱路徑上的第一個頂點是源點，最后一個頂點是終點。關(guān)于最短路徑主要有兩種算法，迪杰斯特拉(Dijkstra) 算法和弗洛伊德(Floyd) 算法。

1. 迪杰斯特拉算法

從某個源點到其余各頂點的最短路徑

對于網(wǎng)N=（V，E），將N中的頂點分成兩組：
第一組S：已求出的最短路徑的終點集合（初始時只包含源點v0）。
第二組V-S：尚未求出最短路徑的終點集合（初始時V-{v0}）。
算法將各項頂點與v0 間最短路徑長度遞增的次序，逐個將集合V-S的頂點加入集合S中去。在這個過程中，總保持從v0到集合S中各頂點的路徑長度始終不大于到集合V-S中各頂點x 的路徑。

算法的實現(xiàn)要引入以下輔助數(shù)據(jù)結(jié)構(gòu)

一位數(shù)組S[i]:記錄從源點v0到終點vi是否已被確定最短路徑長度，true表示確定，false表示尚未確定。
一位數(shù)組Path[i]：記錄從源點v0到終點vi的當(dāng)前最短路徑上vi的直接前驅(qū)頂點序號。其初始值為：如果從v0到vi有弧，則Path[i]為v0,否則為-1。
一位數(shù)組D[i]:記錄從源點v0到終點vi的當(dāng)前最短路徑長度。其初始值為：如果從v0到vi有弧，則D[i]為弧上的權(quán)值，否則為∞。
顯然，長度最短的一條最短路徑必為（v0,vk），滿足以下條件：
D[k] = Min{D[i]|vi∈V-S}
求得頂點vk的最短路徑后，將其加入到第一組頂點集S中。
每當(dāng)加入一個新的頂點到頂點集S，對第二組剩余的各個頂點而言，多一個中轉(zhuǎn)頂點，從而多一個中轉(zhuǎn)路徑，所以要對第二組剩余的各個頂點的最短路徑長度進行更新。
原來v0到vi的最短路徑長度為D[i],加入k作為中間頂點的中轉(zhuǎn)路徑長度為：D[k]+Garcs[k][i],若D[k]+Garcs[k][i]<D[i],則用D[k]+Garcs[k][i]取代D[i]。
更新后，再選擇數(shù)組D中值最小的頂點加入到第一組頂點集S中，如此進行下去，直至圖中所有頂點到第一組頂點集S中為止。