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