在這個問題中給出有向圖G它的每條邊都有一個非負的長度(耗費) a [i ][ j ]路徑的長度即為此路徑所經過的邊的長度之和對於給定的源頂點s需找出從它到圖中其他任意頂點(稱為目的)的最短路徑圖a 給出了一個具有五個頂點的有向圖各邊上的數即為長度假設源頂點s 為從頂點出發的最短路徑按路徑長度順序列在圖b 中每條路徑前面的數字為路徑的長度
利用E Dijkstra發明的貪婪算法可以解決最短路徑問題它通過分步方法求出最短路徑每一步產生一個到達新的目的頂點的最短路徑下一步所能達到的目的頂點通過如下貪婪准則選取在還未產生最短路徑的頂點中選擇路徑長度最短的目的頂點也就是說 D i j k s t r a的方法按路徑長度順序產生最短路徑
首先最初產生從s 到它自身的路徑這條路徑沒有邊其長度為在貪婪算法的每一步中產生下一個最短路徑一種方法是在目前已產生的最短路徑中加入一條可行的最短的邊結果產生的新路徑是原先產生的最短路徑加上一條邊這種策略並不總是起作用另一種方法是在目前產生的每一條最短路徑中考慮加入一條最短的邊再從所有這些邊中先選擇最短的這種策略即是D i j k s t r a算法
可以驗證按長度順序產生最短路徑時下一條最短路徑總是由一條已產生的最短路徑加上一條邊形成實際上下一條最短路徑總是由已產生的最短路徑再擴充一條最短的邊得到的且這條路徑所到達的頂點其最短路徑還未產生例如在圖 中b 中第二條路徑是第一條路徑擴充一條邊形成的;第三條路徑則是第二條路徑擴充一條邊;第四條路徑是第一條路徑擴充一條邊;第五條路徑是第三條路徑擴充一條邊
通過上述觀察可用一種簡便的方法來存儲最短路徑可以利用數組pp [ i ]給出從s 到達i的路徑中頂點i 前面的那個頂點在本例中p [ : ] = [ ]從s 到頂點i 的路徑可反向創建從i 出發按p[i]p[p[i]]p[p[p[i]]] 的順序直到到達頂點s 或在本例中如果從i = 開始則頂點序列為p[i]= p[]= p[]==s因此路徑為
為能方便地按長度遞增的順序產生最短路徑定義d [ i ]為在已產生的最短路徑中加入一條最短邊的長度從而使得擴充的路徑到達頂點i最初僅有從s 到s 的一條長度為的路徑這時對於每個頂點id [ i ]等於a [ s ] [ i ](a 是有向圖的長度鄰接矩陣)為產生下一條路徑需要選擇還未產生最短路徑的下一個節點在這些節點中d值最小的即為下一條路徑的終點當獲得一條新的最短路徑後由於新的最短路徑可能會產生更小的d值因此有些頂點的d值可能會發生變化
綜上所述可以得到圖 所示的偽代碼 ) 將與s 鄰接的所有頂點的p 初始化為s這個初始化用於記錄當前可用的最好信息也就是說從s 到i 的最短路徑即是由s到它自身那條路徑再擴充一條邊得到當找到更短的路徑時 p [ i ]值將被更新若產生了下一條最短路徑需要根據路徑的擴充邊來更新d 的值
) 初始化d[i ] =a[s] [i ](≤i≤n)
對於鄰接於s的所有頂點i置p[i ] =s 對於其余的頂點置p[i ] = ;
對於p[i]≠的所有頂點建立L表
) 若L為空終止否則轉至 )
) 從L中刪除d值最小的頂點
) 對於與i 鄰接的所有還未到達的頂點j更新d[ j ]值為m i n{d[ j ] d[i ] +a[i ][ j ] };若d[ j ]發生了變化且j 還未
在L中則置p[ j ] = 並將j 加入L轉至
圖 最短路徑算法的描述
數據結構的選擇
我們需要為未到達的頂點列表L選擇一個數據結構從L中可以選出d 值最小的頂點如果L用最小堆(見 節)來維護則這種選取可在對數時間內完成由於) 的執行次數為O ( n )所以所需時間為O ( n l o g n )由於擴充一條邊產生新的最短路徑時可能使未到達的頂點產生更小的d 值所以在) 中可能需要改變一些d 值雖然算法中的減操作並不是標准的最小堆操作但它能在對數時間內完成由於執行減操作的總次數為 O(有向圖中的邊數)= O ( n )因此執行減操作的總時間為O ( n l o g n )
若L用無序的鏈表來維護則) 與) 花費的時間為O ( n )) 的每次執行需O(|L | ) =O( n )的時間每次減操作需( )的時間(需要減去d[j] 的值但鏈表不用改變)利用無序鏈表將圖 的偽代碼細化為程序 其中使用了C h a i n (見程序 )和C h a i n I t e r a t o r類(見程序 )
程序 最短路徑程序
template
void AdjacencyWDigraph ::ShortestPaths(int s T d[] int p[])
{// 尋找從頂點s出發的最短路徑 在d中返回最短距離
// 在p中返回前繼頂點
if (s < || s > n) throw OutOfBounds();
Chain L; // 路徑可到達頂點的列表
ChainIterator I;
// 初始化d p L
for (int i = ; i <= n; i++){
d[i] = a[s][i];
if (d[i] == NoEdge) p[i] = ;
else {p[i] = s;
L I n s e r t ( i ) ; }
}
// 更新d p
while (!LIsEmpty()) {// 尋找具有最小d的頂點v
int *v = IInitialize(L);
int *w = INext();
while (w) {
if (d[*w] < d[*v]) v = w;
w = INext();}
// 從L中刪除通向頂點v的下一最短路徑並更新d
int i = *v;
L D e l e t e ( * v ) ;
for (int j = ; j <= n; j++) {
if (a[i][j] != NoEdge && (!p[j] ||
d[j] > d[i] + a[i][j])) {
// 減小d [ j ]
d[j] = d[i] + a[i][j];
// 將j加入L
if (!p[j]) LInsert(j);
p[j] = i;}
}
}
}
若N o E d g e足夠大使得沒有最短路徑的長度大於或等於N o E d g e則最後一個for 循環的i f條件可簡化為if (d[j] > d[i] + a[i][j])) NoEdge 的值應在能使d[j]+a[i][j] 不會產生溢出的范圍內
復雜性分析
程序 的復雜性是O ( n )任何最短路徑算法必須至少對每條邊檢查一次因為任何一條邊都有可能在最短路徑中因此這種算法的最小可能時間為O ( e )由於使用耗費鄰接矩陣來描述圖僅決定哪條邊在有向圖中就需O ( n )的時間因此采用這種描述方法的算法需花費O ( n )的時間不過程序 作了優化(常數因子級)即使改變鄰接表也只會使最後一個f o r循環的總時間降為O ( e )(因為只有與i 鄰接的頂點的d 值改變)從L中選擇及刪除最小距離的頂點所需總時間仍然是O( n )
From:http://tw.wingwit.com/Article/program/sjjg/201311/23592.html
