「圖」與「道路地圖」

把一張圖想像成道路地圖，把圖上的點想像成地點，把圖上的邊想像成道路，把權重想像成道路的長度。若兩點之間以邊相連，表示兩個地點之間有一條道路，道路的長度是邊的權重。

有時候為了應付特殊情況，邊的權重可以是零或者負數，也不必真正照著圖上各點的地理位置來計算權重。別忘記「圖」是用來記錄關聯的東西，並不是真正的地圖。

Walk / Circuit

在圖上任取兩點，分別做為起點和終點，我們可以規劃出許多條由起點到終點的路線。這些路線可以經過其他點，也可以來來回回的繞圈子。一條路線，就是一條「途徑」。

如果起點到終點是不相通的，那麼就不會存在起點到終點的途徑。如果起點和終點一樣，那麼就存在途徑，途徑是一個點、零條邊。

途徑也有權重。途徑經過的每一條邊，沿路加總權重，就是途徑的權重（通常只加總邊的權重，而不考慮點的權重）。途徑的權重，可以想像成途徑的總長度。

至於頭尾相接的途徑則稱作「回路」。

Trail / Circuit

一條途徑，沒有重複地經過同樣的邊，就稱做「跡」。

至於頭尾相接的跡也稱作「回路」。

Path / Cycle

一條途徑，沒有重複地經過同樣的點（與邊），就稱做「路徑」。

至於頭尾相接的路徑則稱作「環」。

【註：關於這些名詞，每個人的定義方式都略有差異，詳見http://planetmath.org/encyclopedia/OpenWalk.html】

Shortest Walk

「最短途徑」，在一張加權圖上，兩點之間權重最小的途徑。最短途徑不見得是邊最少、點最少的途徑。

最短途徑也可能不存在。兩點之間不連通、不存在途徑的時候，也就不會有最短途徑了。

Relaxation

尋找兩點之間的最短途徑時，最直觀的方式莫過於：先找一條途徑，然後再找其他途徑，看看會不會更短，並記住最短的一條。

找更短的途徑並不困難。我們可以尋覓捷徑，以縮短途徑；也可以另闢蹊徑，取代原本的途徑。如此找下去，必會找到最短途徑。

尋覓捷徑、另闢蹊徑的過程，可以以數學方式來描述：現在要找尋起點為s、終點為t的最短途徑，而且現在已經有一條由s到t的途徑，這條途徑上會依序經過a及b這兩點（可以是起點和終點）。我們可以找到一條新的捷徑，起點是a、終點是b的捷徑，以這條捷徑取代原本由a到b的這一小段途徑，讓途徑變短。

找到捷徑以縮短原本途徑，便是Relaxation。

Negative Cycle

權重為負值的環，以下簡稱負環。

有一種情形會讓最短途徑成為無限短：如果一張圖上面有負環，那麼只要建立一條經過負環的捷徑，便會讓途徑縮短一些；只要不斷地建立經過負環的捷徑，反覆地繞行負環，那麼途徑就會無限的縮短下去，成為無限短。

大部分的最短途徑演算法都可以偵測出圖上是否有負環，不過有些卻不行。

無限長與無限短

當起點和終點之間不存在途徑的時候，也就不會有最短途徑了。這種情況有時候會被解讀成：從起點永遠走不到終點，所以最短途徑無限長。

當圖上有負環可做為捷徑的時候，這種情況則是：最短途徑無限短。

沒有負環，那麼Shortest Walk = Shortest Path

除了負環以外，如果一條途徑重複的經過同一條邊、同一個點，一定會讓路徑長度變長。由此可知：沒有負環的情況下，最短途徑都是最短路徑，決不會經過同樣的點兩次，也決不會經過同樣的邊兩次。

當一張圖有負環時，最短途徑無限短，我們無需深入討論；當一張圖沒有負環時，最短途徑就是最短路徑，我們可以專心討論路徑，而非途徑。

Shortest Path Tree

當一張圖沒有負環時，在圖上選定一個點做為起點，由此起點到圖上各點的最短路徑們，會延展成一棵樹，稱作「最短路徑樹」。由於最短路徑不見得只有一條，以特定一點做為起點的最短路徑樹也不見得只有一種。

最短路徑樹上的每一條最短路徑，都是由其它的最短路徑延伸拓展而得（除了由起點到起點這一條最短路徑以外）。也就是說，最短路徑樹上的每一條最短路徑，都是以其他的最短路徑做為捷徑。

當兩點之間有多條邊

當兩點之間有多條邊，可以留下一條權重最小的邊。這麼做不影響最短路徑。

當兩點之間沒有邊

當兩點之間沒有邊（兩點不相鄰），可以補上一條權重無限大的邊。這麼做不影響最短路徑。

當圖的資料結構為adjacency matrix時，任兩點之間都一定要有一個權重值。要找最短路徑，不相鄰的兩點必須設定權重無限大，而不能使用零，以免計算錯誤；要找最長路徑，則是要設定權重無限小。

Shortest Walk、Shortest Path、Longest Walk、Longest Path

「最短途徑」是P問題。

「最短路徑」已被證明是NP-Complete問題。圖上沒有負環時，才是P問題。

【註：古早人把walk叫做path、把path叫做simple path。早期論文說shortest path是P問題，純粹是因為古早人與現代人用了不同的名詞定義。古早人的定義，眼光不夠長遠，已經不合時宜，成為歷史包袱了。】

「最長途徑」，兩點之間權重最大的途徑。只要把每一條邊的權重都添上負號，就變成最短途徑問題了。

「最長路徑」，兩點之間權重最大的路徑。只要把每一條邊的權重都添上負號，就變成最短路徑問題了。

最短路徑演算法的功能類型

Point-to-Point Shortest Path，點到點最短路徑：給定起點、終點，求出起點到終點的最短路徑。一對一。

Single Source Shortest Paths，單源最短路徑：給定起點，求出起點到圖上每一點的最短路徑。一對全。

All Pairs Shortest Paths，全點對最短路徑：求出圖上所有兩點之間的最短路徑。全對全。

最短路徑演算法的原理類型，有向圖

Label Setting：逐步設定每個點的最短路徑長度值，一旦設定後就不再更改。

Label Correcting：設定某個點的最短路徑長度值之後，之後仍可繼續修正其值，越修越美。整個過程就是不斷重新標記每個點的最短路徑長度值。

註：Label是指在圖上的點（或邊）標記數值或符號。

最短路徑演算法的原理類型，無向圖

需精通「Matching」、「Circuit」、「T-Join」等進階概念，因此以下文章不討論！

一般來說，當無向圖沒有負邊，尚可套用有向圖的演算法。當無向圖有負邊，則必須使用「T-Join」。

最短途徑、最短路徑解法列表

　　　　　　　　　無負邊　　　　　有負邊　　　　　　有負邊
　　　　　　　　　　　　　　　　　無負環　　　　　　有負環
有向圖　最短途徑　等同最短路徑　　等同最短路徑　　　無限短
　　　　最短路徑　Label Setting 　Label Correcting　NP-complete
無向圖　最短途徑　等同最短路徑　　無限短　　　　　　無限短
　　　　最短路徑　Label Setting 　T-Join　　　　　　NP-complete
混合圖　最短途徑　?          　　 ?           　　　?
　　　　最短路徑　NP-complete 　　NP-complete 　　　NP-complete

註：無限短的情況，必須與負邊、負環相連通。

用途

在一張有向圖上面選定一個起點後，此演算法可以求出此點到圖上各點的最短路徑，即是最短路徑樹。但是限制是：圖上每一條邊的權重皆非負數。

演算法

當圖上每一條邊的權重皆非負數時，可以發現：每一條最短路徑，都是邊數更少、權重更小（也可能相同）的最短路徑的延伸。

於是乎，建立最短路徑樹，可以從邊數較少的最短路徑開始建立，然後逐步延伸拓展。換句話說，就是從距離起點最近的點和邊開始找起，然後逐步延伸拓展。先找到的點和邊，保證會是最短路徑樹上的點和邊。

也可以想成是，從目前形成的最短路徑樹之外，屢次找一個離起點最近的點，（連帶著邊）加入到最短路徑樹之中，直到圖上所有點都被加入為止。

整個演算法的過程，可看作是兩個集合此消彼長。不在樹上、離根最近的點，移之。

循序漸進、保證最佳，這是Greedy Method的概念。

一點到多點的最短路徑、求出最短路徑樹

1. 將起點加入到最短路徑樹。此時最短路徑樹只有起點。
2. 重複下面這件事V-1次，將剩餘所有點加入到最短路徑樹。
　甲、尋找一個目前不在最短路徑樹上而且離起點最近的點b。
　乙、將b點加入到最短路徑樹。

這裡提供一個簡單的實作。運用Memoization，建立表格紀錄已求得的最短路徑長度，便容易求得不在樹上、離根最近的點。時間複雜度是O(V^3)。

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都是空的。

1. 將起點加入到最短路徑樹。此時最短路徑樹只有起點。
2. 重複下面這件事V-1次，將剩餘所有點加入到最短路徑樹。
　甲、尋找一個目前不在最短路徑樹上而且離起點最近的點：
　　　以窮舉方式，
　　　找一個已在最短路徑樹上的點a，以及一個不在最短路徑樹上的點b，
　　　讓d[a]+w[a][b]最小。
　乙、將b點的最短路徑長度存入到d[b]之中。
　丙、將b點（連同邊ab）加入到最短路徑樹。

實作

int w[9][9]; // 一張有權重的圖：adjacency matrix int d[9]; // 紀錄起點到圖上各個點的最短路徑長度 int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰 bool visit[9]; // 紀錄各個點是不是已在最短路徑樹之中 void label_setting(int source) { for (int i=0; i<100; i++) visit[i] = false; // initialize d[source] = 0; // 設定起點的最短路徑長度 parent[source] = source; // 設定起點是樹根（父親為自己） visit[source] = true; // 將起點加入到最短路徑樹 for (int k=0; k<9-1; k++) // 將剩餘所有點加入到最短路徑樹 { // 從既有的最短路徑樹，找出一條聯外而且是最短的邊 int a = -1, b = -1, min = 1e9; // 找一個已在最短路徑樹上的點 for (int i=0; i<9; i++) if (visit[i]) // 找一個不在最短路徑樹上的點 for (int j=0; j<9; j++) if (!visit[j]) if (d[i] + w[i][j] < min) { a = i; // 記錄這一條邊 b = j; min = d[i] + w[i][j]; } // 起點有連通的最短路徑都已找完 if (a == -1 || b == -1) break; // // 不連通即是最短路徑長度無限長 // if (min == 1e9) break; d[b] = min; // 儲存由起點到b點的最短路徑長度 parent[b] = a; // b點是由a點延伸過去的 visit[b] = true; // 把b點加入到最短路徑樹之中 } }

換個角度看事情

前面有提到relaxtion的概念。以捷徑的觀點來看，當下已求得的每一條最短路徑，都會作為捷徑，縮短所有由起點到圖上各點的路徑。每個步驟中所得到的最短路徑，由於比它更短的最短路徑全都嘗試做為捷徑過了，所以能夠確保是最短路徑。

Label Setting Algorithm亦可看做是一種Graph Traversal，但與BFS和DFS不同的地方在於Label Setting Algorithm有考慮權重，遍歷順序是先拜訪離樹根最近的點和邊。

想法

找不在樹上、離根最近的點，先前的方式是：窮舉樹上a點及非樹上b點，找出最小的d[a]+w[a][b]。

以w[a][b]的角度來看，整個過程重覆窮舉了許多邊。

運用Memoization，隨時紀錄已經窮舉過的邊，避免重複窮舉，節省時間。

每當將一個a點加入最短路徑樹，就將d[a]+w[a][b]存入d[b]。找不在樹上、離根最近的點，就直接窮舉d[]表格，找出最小的d[b]。

演算法

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都設為無限大。

1. 重複下面這件事V次，以將所有點加入到最短路徑樹。
　甲、尋找一個目前不在最短路徑樹上而且離起點最近的點：
　　　直接搜尋d[]陣列裡頭的數值，來判斷離起點最近的點。
　乙、將此點加入到最短路徑樹之中。
　丙、令剛剛加入的點為a點，
　　　以窮舉方式，找一個不在最短路徑樹上、且與a點相鄰的點b，
　　　把d[a]+w[a][b]存入到d[b]當中。
　　　因為要找最短路徑，所以儘可能紀錄越小的d[a]+w[a][b]。
　　　（即是邊ab進行relaxation）

時間複雜度

分為兩個部分討論。

甲、加入點、窮舉邊：每個點只加入一次，每條邊只窮舉一次，剛好等同於一次Graph Traversal的時間。

乙、尋找下一個點：從大小為V的陣列當中尋找最小值，為O(V)；總共尋找了V次，為O(V^2)。

甲乙相加就是整體的時間複雜度。圖的資料結構為adjacency matrix的話，便是O(V^2)；圖的資料結構為adjacency lists的話，還是O(V^2)。

實作

int w[9][9]; // 一張有權重的圖 int d[9]; // 紀錄起點到各個點的最短路徑長度 int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰 bool visit[9]; // 紀錄各個點是不是已在最短路徑樹之中 void dijkstra(int source) { for (int i=0; i<9; i++) visit[i] = false; // initialize for (int i=0; i<9; i++) d[i] = 1e9; d[source] = 0; parent[source] = source; for (int k=0; k<9; k++) { int a = -1, b = -1, min = 1e9; for (int i=0; i<9; i++) if (!visit[i] && d[i] < min) { a = i; // 記錄這一條邊 min = d[i]; } if (a == -1) break; // 起點有連通的最短路徑都已找完 // if (min == 1e9) break; // 不連通即是最短路徑長度無限長 visit[a] = true; for (b=0; b<9; b++) // 把起點到b點的最短路徑當作捷徑 if (!visit[b] && d[a] + w[a][b] < d[b]) { d[b] = d[a] + w[a][b]; parent[b] = a; } } } // 若要找出某一點的最短路徑，就可以利用parent陣列了。 void find_path(int x) // 印出由起點到x點的最短路徑 { if (x != parent[x]) // 先把之前的路徑都印出來 find_path(parent[x]); cout << x << endl; // 再把現在的位置印出來 } struct Element {int b, w;} lists[9]; // 一張有權重的圖 int size[9]; int d[9]; int parent[9]; bool visit[9]; void dijkstra(int source) { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) d[i] = 1e9; d[source] = 0; parent[source] = source; for (int k=0; k<9; k++) { int a = -1, b = -1, min = 1e9; for (int i=0; i<100; i++) if (!visit[i] && d[i] < min) { a = i; min = d[i]; } if (a == -1) break; visit[a] = true; for (int i=0; i<size[a]; i++) { int b = lists[a][i].b, w = lists[a][i].w; if (!visit[b] && d[a] + w < d[b]) { d[b] = d[a] + w; parent[b] = a; } } } } struct Edge {int a, b, w;}; // 紀錄一條邊的資訊 Edge edges[13]; int d[9]; int parent[9]; bool visit[9]; void dijkstra(int source) { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) d[i] = 1e9; d[source] = 0; parent[source] = source; for (int k=0; k<9; k++) { int a = -1, b = -1, min = 1e9; for (int i=0; i<100; i++) if (!visit[i] && d[i] < min) { a = i; min = d[i]; } if (a == -1) break; visit[a] = true; for (int i=0; i<13; i++) if (edges[i].a == a) { int b = edges[i].b, w = edges[i].w; if (!visit[b] && d[a] + w < d[b]) { d[b] = d[a] + w; parent[b] = a; } } } }

換個角度看事情

一條比較長的最短路徑，移除尾端一小段後，就變成了一條比較短的最短路徑。有分割問題的味道。利用這一點，我們可以製造出遞迴公式，並利用Dynamic Programming解題。Dijkstra's Algorithm可以看做是bottom-up、往後補值的DP。

延伸閱讀：Fibonacci Heap

用特殊的資料結構可以加快這個演算法。建立V個元素的Fibonacci Heap，用其decrease key函式來實作relaxation，用其extract min函式來找出下一個點，可將時間複雜度降至O(E+VlogV)。

UVa 10801 10841 10278 10187 10039

演算法

找不在樹上、離根最近的點，也可以直接把d[a]+w[a][b]的值通通倒進Priority Queue。

每次要尋找一個離起點最近的點，就直接從Priority Queue拿出一個最近的點；每次relaxation，就把更新過的點塞入Priority Queue。

這裡提供一種實作。讀過State Space Search這個章節的讀者，可發現這個實作便是Uniform-cost Search，因此也有人說這個實作是考慮權重的BFS。

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都是空的。
令PQ是一個存放點的Priority Queue，由小到大排序鍵值。

1. 把起點放入PQ。
2. 重複下面這件事，直到最短路徑樹完成為止：
　甲、嘗試從PQ中取出一點a，點a必須是目前不在最短路徑樹上的點。
　乙、將a點（連同其邊）加入最短路徑樹。
　丙、將所有與a點相鄰且不在樹上的點b（連同邊ab）放入PQ，
　　　設定鍵值為d[a] + w[a][b]。
　　　（此步驟即是以邊ab進行ralaxation。）

struct Node // 要丟進Priority Queue的點 { int a, p, d; // a是點，p是a的父親，d是可能的最短路徑長度。 // constructor，方便建立Vertex物件，方便編寫程式碼。 Node(int a, int p, int d): a(a), p(p), d(d) { /* empty */ } // C++ STL內建的Priority Queue是Max-Heap，不是Min-Heap， // 故必須改寫一下比大小的函式。 bool operator<(const Node& n) const { return d > n.d; } }; int w[9][9]; int d[9]; int parent[9]; bool visit[9]; void label_setting_with_priority_queue(int source) { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) d[i] = 1e9; priority_queue<Node> PQ; // C++ STL的Priority Queue PQ.push( Node(source, source, 0) ); // 放入起點 for (int i=0; i<9; i++) { // 找出下一個要加入到最短路徑樹的點 Node n; while (!PQ.empty()) { n = PQ.top(); PQ.pop(); if (!visit[n.a]) break; } // 起點有連通的最短路徑都已找完 if (PQ.empty()) break; int a = n.a; d[a] = n.d; parent[a] = n.p; visit[a] = true; // 將比大小的工作交由Priority Queue來做 for (int b=0; b<9; b++) if (!visit[b]) PQ.push( Node(b, a, d[a] + w[a][b]) ); } }

這裡提供一種更好的實作，是Dijkstra's Algorithm加上Priority Queue。

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都是空的。
令PQ是一個存放點的Priority Queue，由小到大排序鍵值。

1. 把起點放入PQ。
2. 重複下面這件事，直到最短路徑樹完成為止：
　甲、嘗試從PQ中取出一點a，點a必須是目前不在最短路徑樹上的點。
　乙、將a點（連同其邊）加入最短路徑樹。
　丙、將所有與a點相鄰且不在樹上的點的點b（連同邊ab）放入PQ，
　　　設定鍵值為d[a] + w[a][b]，鍵值同時也存入d[b]，
　　　但是會先檢查d[a] + w[a][b]是不是大於d[b]，
　　　大於才放入PQ，鍵值才存入d[b]。
　　　（此步驟即是以邊ab進行ralaxation。）

struct Node // 要丟進Priority Queue的點 { int a, d; // a是點，d是可能的最短路徑長度。 // p可以提出來，不必放在Node裡。 // constructor，方便建立Vertex物件，方便編寫程式碼。 Node(int a, int d): a(a), d(d) { /* empty */ } // C++ STL內建的Priority Queue是Max-Heap，不是Min-Heap， // 故必須改寫一下比大小的函式。 bool operator<(const Node& n) const { return d > n.d; } }; int w[9][9]; int d[9]; int parent[9]; bool visit[9]; void dijkstra_with_priority_queue(int source) { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) d[i] = 1e9; parent[source] = source; priority_queue<Node> PQ; // C++ STL的Priority Queue PQ.push( Node(source, 0) ); // 放入起點 for (int i=0; i<9; i++) { // 找出下一個要加入到最短路徑樹的點 Node n; while (!PQ.empty()) { n = PQ.top(); PQ.pop(); if (!visit[n.a]) break; } // 起點有連通的最短路徑都已找完 if (PQ.empty()) break; int a = n.a; d[a] = n.d; visit[a] = true; // 將比大小的工作交由Priority Queue來做 for (int b=0; b<9; b++) if (!visit[b] && d[a] + w[a][b] < d[b]) { d[b] = d[a] + w[a][b]; parent[b] = a; PQ.push( Node(b, d[a] + w[a][b]) ); } } }

時間複雜度：操作Priority Queue

分為兩種情形討論。

一、將點放入Priority Queue的時間：

首先要確定Priority Queue的大小才行。根據先前的說明，可以發現Priority Queue裡頭全部都是經過relaxation之後的點。以邊的觀點來思考，圖上的每條邊剛好都會用於relaxation一次，一條邊對應一個塞入Priority Queue的點，所以Priority Queue前前後後一共塞入了E個點，大小為O(E)。

所以，塞入一個點到Priority Queue需時O(logE)，前前後後一共塞入了E個點，所以維護Priority Queue的時間為O(ElogE)。

二、將點拿出Priority Queue的時間：

要建立最短路徑樹，只要從Priority Queue取出V個點即可。取出一個點需時O(logE)，故取出V個點需時O(VlogE)。

綜合第一點和第二點，Priority Queue的操作共需時O(ElogE)。

在最短路徑問題當中，如果兩點之間有多條邊，只要取權重比較小的邊來進行最短路徑演算法就行了。也就是說，兩點之間只會剩下一條邊。也就是說，邊的總數不會超過C{V,2} = V*(V-1)/2個。也就是說，這個方法的時間複雜度O(ElogE)，可改寫成O(Elog(V^2)) = O(2ElogV) = O(ElogV)。

Priority Queue可以採用Binary Heap或Binomial Heap，時間複雜度都相同。:)

當圖上每條邊的權重皆為正整數的情況下，Priority Queue亦可以採用vEB Tree，時間複雜度會變成O(EloglogW)，其中W為最長的最短路徑長度值。

時間複雜度

一次Graph Traversal的時間，再加上操作Priority Queue的時間。

圖的資料結構為adjacency matrix的話，便是O(V^2 + ElogE)；圖的資料結構為adjacency lists的話，便是O(V+E + ElogE)。

這個方法適用於圖上的邊非常少的情況。若是一般情況，使用原本的Dijkstra's Algorithm會比較有效率，程式碼的結構也較簡單。

UVa 10278 10740 10986

演算法

找不在樹上、離根最近的點，也可以直接把d[a]+w[a][b]的值通通拿去做Bucket Sort。特別適合用在每條邊的權重都是非負整數的圖上。

下面題供一個實作方式，每個bucket使用了Dijkstra's Algorithm的表格手法，以達到比較好的時間複雜度。一般的方式是以一個priority queue來實作一個bucket。

float w[9][9]; float d[9]; int parent[9]; bool visit[9]; float bucket_dist[500][9]; // 建立500個bucket int bucket_parent[500][9]; bool bucket_visit[500][9]; void push(int v, float d, int p) { int slot = d; // 此處等同於floor(d) bucket_dist[slot][v] = d; bucket_parent[slot][v] = p; n++; } int extract_min(int slot) { float min = 1e9; int v = -1; for (int i=0; i<bucket_size[slot]; i++) if (!bucket_extract[slot][i] && bucket_dist[slot][i] < min) min = bucket_dist[slot][i], v = i; bucket_visit[slot][v] = true; return v; } void dial(int source) { memset(visit, false, sizeof(visit)); // initialize memset(bucket_visit, false, sizeof(bucket_visit)); push(source, 0, source); int index = 0; for (int k=0, slot=0; k<9 && slot<500; k++) { int a, b; while (slot < 500 && (a = extract_min(slot)) == -1) slot++; if (slot == 500) break; // 起點有連通的最短路徑都已找完 visit[a] = true; parent[a] = bucket_parent[slot][a]; d[a] = bucket_dist[slot][a]; for (b=0; b<9; b++) // 把起點到b點的最短路徑當作捷徑 if (!visit[b]) push(b, d[a] + w[a][b], a); } }

時間複雜度：進行Bucket Sort

一個bucket最多能有E個點，但是一個bucket最多只找V次最小值。所以總共是O(WV)，其中W為bucket的數目，也是最長的最短路徑長度值。

時間複雜度

一次Graph Traversal的時間，再加上進行Bucket Sort的時間。

圖的資料結構為adjacency matrix的話，便是O(V^2 + WV)；圖的資料結構為adjacency lists的話，便是O(V+E + WV)。

值得一提的是，當圖上每條邊的權重皆為非負整數時，會有更好的時間複雜度。圖的資料結構為adjacency matrix的話，便是O(V^2 + W)；圖的資料結構為adjacency lists的話，便是O(V+E + W)。

註記

大眾認知的Bellman-Ford Algorithm並非正確版本，實際上應是Distance Vector Algorithm。許多書籍都有誤植情形，包括著名的CLRS。http://www.walden-family.com/public/bf-history.pdf。

正確的Bellman-Ford Algorithm寡為人知。此演算法曾經由西南交通大学段凡丁《关于最短路径的SPFA快速算法》重新發現，而在中文網路上有著Shortest Path Faster Algorithm, SPFA的非正式稱呼。

此演算法的貢獻者除了Bellman與Ford以外，其實還有另外一人Moore，因此有人稱呼此演算法為Bellman-Ford-Moore Algorithm。按照論文發表的年代順序，Ford首先發現Label Correcting的技巧，但是沒有特別規定計算順序；Moore發現由起點開始，不斷朝鄰點擴展，可作為計算順序（事實上就是以queue實作）；Bellman發現此演算法可套用Dynamic Programming的思路，並證明每個點最多重新標記V-1次，演算法就可以結束。

用途

在一張有向圖上面選定一個起點後，此演算法可以求出此點到圖上各點的最短路徑，即是最短路徑樹，順便偵測圖上是否有負環。

當圖上有負邊時，Label Setting Algorithm就無法使用，因為當下不在樹上、離根最近的點，其距離不見得是最短路徑長度。當圖上有負邊時，可以改用Label Correcting Algorithm，就算數值標記錯了，仍可修正。

演算法：求出最短路徑樹

回想一下，前面介紹relaxation說到：找到捷徑以縮短原本路徑。事實上，只要努力不懈地找捷徑，終會得到最短路徑。

一條捷徑如果很長，就不好辦了。一條捷徑如果很長，可以拆解成一條一條的邊，並一一嘗試以這些邊做為捷徑。只要不斷重複嘗試，一條一條的邊終會連接成一條完整的捷徑。

一開始想要不斷找捷徑，然而捷徑太多太長，只好多條捷徑拆解成一條條捷徑，一條捷徑拆成一條條邊，最後以邊為單位來進行relaxation，不斷重複利用目前算得的最短路徑長度值，這是Greedy Method的概念。

以relaxation的角度來看，Label Setting Algorithm與Label Correcting Algorithm的差異在於：Label Setting Algorithm知道該由哪個順序開始進行relaxation，所以可以逐步的設定好每個點的最短路徑長度值；Label Correcting Algorithm不知道正確順序，所以就只好不斷找捷徑，不斷校正每個點的最短路徑長度，直到正確為止。

演算法：偵測負環

如果一張圖上面有負環，那麼只要建立一條經過負環的捷徑，便會讓路徑縮短一些；只要不斷地建立經過負環的捷徑，反覆地繞行負環，那麼路徑就會可以無限的縮短下去，成為無限短。

一條最短路徑最多只有V-1條邊。當發現一個點被標記超過V-1次，表示其最短路徑超過V-1條邊（讀者請自行推敲），超過V-1條邊則必定經過負環！

附帶一提，Label Correcting Algorithm可以偵測圖中是否存在負環，但是無法找出負環所在，也無法找出所有負環。

演算法

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都設為無限大。

1. 重複下面這件事，直到圖上每一條邊都無法作為捷徑：
　甲、找到一條可以做為捷徑的邊ab：d[a] + w[a][b] < d[b]。
　乙、以邊ab來修正起點到b點的最短路徑：d[b] = d[a] + w[a][b]。
　丙、如果b點被標記V次以上，表示圖上有負環。演算法立刻結束。

int w[9][9]; // 一張有權重的圖：adjacency matrix int d[9]; // 紀錄起點到各個點的最短路徑長度 int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰 int n[9]; // 記錄各個點被標記幾次，初始化為零。 void label_correcting(int source) { n[0...9-1] = 0; // 初始化 d[source] = 0; // 設定起點的最短路徑長度 parent[source] = source; // 設定起點是樹根（父親為自己） n[source]++; // 起點被標記了一次 while (還能找到一條邊ab讓d[a] + w[a][b] < d[b]) { d[b] = d[a] + w[a][b]; // 更新由起點到b點的最短路徑長度 parent[b] = a; // b點是由a點延伸過去的 if (++n[b] >= 9) return;// 圖上有負環，最短路徑樹不存在！ } }

時間複雜度

每個點最多被標記V次，一個點一旦被重新標記後，就要讓該點所有出邊都嘗試進行relaxation。

每個點剛好都被標記一次時，就需時O(V+E)；每個點剛好都被標記V次時，就需時O(V*(V+E))，可簡單寫成O(VE)。

所以建立最短路徑樹順便偵測負環，時間複雜度總共為O(VE)。

實作

這裡提供一個常見的實作。用個容器把剛修正過的點暫存起來，以便後續修正。

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都設為無限大。
LIST是一個存放點的容器，可以是stack、queue、set、……。

1. 把起點放入LIST。
2. 重複下面這件事，直到LIST沒有東西為止：
　甲、從LIST中取出一點，作為a點。
　乙、找到一條可以做為捷徑的邊ab：d[a] + w[a][b] < d[b]。
　丙、以邊ab來修正起點到b點的最短路徑：d[b] = d[a] + w[a][b]。
　丁、將b點加到LIST當中。
　戊、如果b點被標記V次以上，表示圖上有負環。演算法立刻結束。

int w[9][9]; // 一張有權重的圖：adjacency matrix int d[9]; // 紀錄起點到各個點的最短路徑長度 int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰 int n[9]; // 記錄各個點被標記幾次，初始化為零。 void label_correcting(int source) { memset(n, 0, sizeof(n)); // 初始化 d[source] = 0; // 設定起點的最短路徑長度 parent[source] = source; // 設定起點是樹根（父親為自己） n[source]++; // 起點被標記了一次 queue<int> Q; // 一個存放點的容器：queue Q.push(source); // 將起點放入容器當中 while (!Q.empty()) { int a = Q.top(); Q.pop(); // 從容器中取出一點，作為a點 for (int b=0; b<9 ++b) if (d[a] + w[a][b] < d[b]) { if (++n[b] >= 9) return;// 圖上有負環，最短路徑樹不存在 d[b] = d[a] + w[a][b]; // 修正起點到b點的最短路徑長度 parent[b] = a; // b點是由a點延伸過去的 Q.push(b); // 將b點放入容器當中 } } }

這個實作看起來就像是Dijkstra's Algorithm的精簡版。Dijkstra's Algorithm是一旦標記過的點就不再標記，至於Label Correcting Algorithm則是標記過的點可以再標記，差在這裡而已。

容器的部分也可以改用Priority Queue，自行訂立一套適當的優先順序，來加速演算法。Small Label First（SLF）、Large Label Last（LLL）都是不錯的選擇。

UVa 10557 10682

用途

在一張有向圖上面選定一個起點後，此演算法可以求出此點到圖上各點的最短路徑，即是最短路徑樹，順便偵測圖上是否有負環。

特別適合用在能夠做平行處理的平台上，例如網路。

【註： 許多書籍稱呼此演算法為Bellman-Ford Algorithm，應是誤植。經過考察，此演算法應是Bellman-Ford-Moore Algorithm的其中一種實作方式，而且是效率最差的實作方式。】

演算法：找出最短路徑樹

可以視作是Label Correcting Algorithm的窮舉版本。全部的邊都當作捷徑，同時（依序）進行relaxation。重覆V-1次。

令w[a][b]是a點到b點的距離（即是邊的權重）。
令d[a]是起點到a點的最短路徑長度，起點設為零，其他點都設為無限大。

1. 重複下面這件事V-1次：
　甲、窮舉所有邊ab。
　乙、找到所有可以做為捷徑的邊ab：d[a] + w[a][b] < d[b]。
　丙、以邊ab來修正起點到b點的最短路徑：d[b] = d[a] + w[a][b]。

時間複雜度與Label Correcting Algorithm相同，但是效率上不如Label Correcting Algorithm。

int w[9][9]; // 一張有權重的圖 int d[9]; // 紀錄起點到各個點的最短路徑長度 int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰 void distance_vector(int source) { for (int i=0; i<9; i++) d[i] = 1e9; // initialize d[source] = 0; // 設定起點的最短路徑長度 parent[source] = source; // 設定起點是樹根（父親為自己） for (int i=0; i<9-1; i++) // 重覆步驟V-1次 for (int a=0; a<9; ++a) // 全部的邊都當作捷徑 for (int b=0; b<9; ++b) if (d[a] + w[a][b] < d[b]) { d[b] = d[a] + w[a][b]; parent[b] = a; } } struct Element {int v, w;} w[9]; // 一張有權重的圖 int size[9]; int d[9]; int parent[9]; void distance_vector(int source) { for (int i=0; i<9; i++) d[i] = 1e9; d[source] = 0; parent[source] = source; for (int i=0; i<9-1; i++) for (int a=0; a<9; a++) for (int j=0; j<size[a]; j++) { int b = w[a][j].b, w = w[a][j].w; if (d[a] + w < d[b]) { d[b] = d[a] + w; parent[b] = a; } } } struct Edge {int a, b, w;}; // 紀錄一條邊的資訊 Edge w[13]; // 將所有邊依序放進陣列之中，成為一張有權重的圖 int d[9]; int parent[9]; void distance_vector(int source) { for (int i=0; i<9; i++) d[i] = 1e9; d[source] = 0; parent[source] = source; for (int i=0; i<9-1; i++) for (int j=0; j<13; j++) { int a = w[j].a, b = w[j].b, w = w[j].w; if (d[a] + w < d[b]) { d[b] = d[a] + w; parent[b] = a; } } }

演算法：偵測負環

由於Distance Vector Algorithm重覆了V-1次，理論上來說，已經把長度為V-1個邊以下、沒有負環的最短路徑都找出來了。如果真的是沒有負環的最短路徑，就不會再有捷徑。因此，如果還能再找到捷徑，那麼該條最短路徑就絕對包含負環。

只需一次Graph Traversal的時間，便能偵測負環。

bool negative_cycle() { for (int a=0; a<9; ++a) for (int b=0; b<9; ++b) if (d[a] + w[a][b] < d[b]) return true; return false; }

UVa 558

用途

在一張有向圖上面選定一個起點後，此演算法可以求出此點到圖上各點的最短路徑，即是最短路徑樹。但是限制是：圖上每一條邊的權重皆非負整數。

演算法（Gabow's Algorithm）

詳細內容可參考CLRS習題24-4，此處僅略述。

重複以下步驟O(logC)次，每個步驟要求出當下的最短路徑：
1. 令權重更加精細。
2. 以上一步驟算得的最短路徑長度來調整權重。
   並以調整後的權重求最短路徑，可用O(V+E)時間求得。
   （調整過的權重剛好皆為非負數，且最短路徑長度都不會超過E。）
3. 還原成正確的最短路徑長度。

Scaling的精髓，在於每次增加精細度後，必須有效率的修正前次與今次的誤差。此演算法巧妙運用調整權重的技術，確切找出前次與今次差異之處，而得以用O(E)時間修正誤差。

上述O(V+E)求最短路徑的演算法，仍是運用Dijkstra's Algorithm「最近的點先找」概念，只是求法有點小改變。首先開個E+1條linked list，離起點距離為x的點，就放在第x條。只要依序掃描一遍所有的linked list，就可以求出最短路徑了。

const int V = 9, E = 9 * 8 / 2; int w[9][9]; // 一張有權重的圖（adjacency matrix） int d[9]; // 紀錄起點到各個點的最短路徑長度 void shortest_path(int s) { vector<int> list[E+1]; list[0].push_back(s); for (int i=0; i<=E; ++i) for (int j=0; j<list[i].size(); ++j) { int u = list[i][j]; if (d[u] is not filled) { d[u] = i; // relaxation for (int v=0; v<V; ++v) if (d[v] is not filled && i + w[u][v] <= E) list[i + w[u][v]].push_back(v); } } }

時間複雜度

整個演算法共有O(logC)個步驟，C是整張圖權重最大的邊的權重。

圖的資料結構為adjacency matrix的話，每一步驟需要O(V^2)時間，整體時間複雜度為O(V^2 * logC)；圖的資料結構為adjacency lists的話，每一步驟需要O(V+E)時間（簡單記為O(E)），整體時間複雜度為O(ElogC)。

計算最短路徑的長度（adjacency lists）

【待補程式碼】

找出最短路徑樹（adjacency lists）

【待補程式碼】

用途

在一張有向無環圖（Directed Acyclic Graph, DAG）上面選定一個起點後，此演算法可以求出此點到圖上各點的最短路徑，即是最短路徑樹。

演算法

此演算法為Topological Sort加上Dynamic Programming，與Activity on Edge Network的演算法如出一轍，可參考本站文件「Topological Sort」。

一張圖經過Topological Sort之後，便可以確定圖上每一個點只會往排在後方的點走去（由排在前方的點走過來）。計算順序相當明確，因此可以利用Dynamic Programming來計算各條最短路徑。

1. 進行Topological Sort。
2. 依照拓樸順序（或者逆序），對各點進行relaxation。

這個演算法可以看做是，每次都知道最小值在哪一點的Dijkstra's Algorithm。

時間複雜度

時間複雜度約是兩次Graph Traversal的時間複雜度。圖的資料結構為adjacency matrix的話，便是O(V^2)；圖的資料結構為adjacency lists的話，便是O(V+E)。

找出最短路徑樹（adjacency matrix）

bool w[9][9]; // adjacency matrix int topo[9]; // 經過拓樸排序後的順序 int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰 void shortest_path_tree(int source) { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) d[i] = 1e9; // 找出起點是在拓樸排序中的哪一個位置 int p = 0; while (p < 9 && topo[p] != source) p++; // 計算最短路徑長度 d[p] = 0; // 設定起點的最短路徑長度 parent[p] = p; // 設定起點是樹根（父親為自己） for (int i=p; i<9; ++i) // 看看每一個點可連向哪些點 for (int j=i+1; j<9; ++j) { int a = topo[i], b = topo[j]; if (d[a] + w[a][b] < d[b]) { d[b] = d[a] + w[a][b]; parent[b] = a; } } }

迴圈的部分還有另一種寫法。

for (int j=p+1; j<9; ++j) // 看看每一個點被哪些點連向 for (int i=0; i<j; ++i) { int a = topo[i], b = topo[j]; if (d[a] + w[a][b] < d[b]) { d[b] = d[a] + w[a][b]; parent[b] = a; } }

UVa 10000 10166 10350 10917