用途

一張有向圖，找出所有兩點之間的最短路徑。

演算法

「Warshall's algorithm」套用到最短路徑問題。

d(i, j, k) = min( d(i, k, k-1) + d(k, j, k-1), d(i, j, k-1) )
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^
                  經過第k點                    沒有經過第k點

d(i, j, k)：由i點到j點的最短路徑長度。中繼點只能是第0點到第k點。

兩點之間的所有路徑，依照中繼點來分類。

一條路徑的中繼點，可能有第0點、第1點、…… 第V-1點。現在把i點到j點的路徑分成兩種：經過第V-1點、未經過第V-1點。接著兩種再各自細分為：經過第V-2點、未經過第V-2點。如此不斷細分下去直到：經過第0點、未經過第0點。

時間複雜度

時間複雜度O(V³)，空間複雜度O(V²)。由於計算順序以及最小值運算的關係，記憶體得以重複使用，只需要二維陣列。

演算法：找出所有兩點之間最短路徑長度

bottom-up dynamic programming，三層迴圈填表格。逐次添加一個中繼點，更新所有路徑長度。

int w[9][9]; // adjacency matrix int d[9][9]; // 最短路徑長度 void floyd_warshall() { for (int i=0; i<9; i++) for (int j=0; j<9; j++) d[i][j] = w[i][j]; for (int i=0; i<9; i++) d[i][i] = 0; for (int k=0; k<9; k++) // 嘗試每一個中繼點 for (int i=0; i<9; i++) // 計算每一個i點與每一個j點 for (int j=0; j<9; j++) if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]; }

演算法：找出所有兩點之間最短路徑

兩種記錄最短路徑的方法：紀錄中繼點、紀錄第二點。

int w[9][9]; int d[9][9]; int medium[9][9]; // 由i點到j點的路徑，其中繼點為medium[i][j]。 void floyd_warshall() { for (int i=0; i<9; i++) for (int j=0; j<9; j++) { d[i][j] = w[i][j]; medium[i][j] = -1; // 預設為沒有中繼點 } for (int i=0; i<9; i++) d[i][i] = 0; for (int k=0; k<9; k++) for (int i=0; i<9; i++) for (int j=0; j<9; j++) if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; medium[i][j] = k; // 由i點走到j點經過了k點 } } // 這支函式並不會印出起點和終點，必須另行印出。 void find_path(int s, int t) // 印出最短路徑 { if (medium[s][t] == -1) return; // 沒有中繼點就結束 find_path(s, medium[s][t]); // 前半段最短路徑 cout << medium[s][t]; // 中繼點 find_path(medium[s][t], t); // 後半段最短路徑 } int w[9][9]; int d[9][9]; int next[9][9]; // 由i點到j點的路徑，第二點為next[i][j]。 void floyd_warshall() { for (int i=0; i<9; i++) for (int j=0; j<9; j++) { d[i][j] = w[i][j]; next[i][j] = j; // 一開始沒有中繼點，所以第二點就是終點。 } for (int i=0; i<9; i++) d[i][i] = 0; for (int k=0; k<9; k++) for (int i=0; i<9; i++) for (int j=0; j<9; j++) if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; // 由i點到j點的路徑的第二點， // 正是由i點到k點的路徑的第二點。 next[i][j] = next[i][k]; } } // 遞迴版 void find_path(int s, int t) // 印出最短路徑 { cout << s; // 第一點 if (s != t) find_path(next[s][t], t); // 第二點以後的最短路徑 } // 迴圈版 void find_path(int s, int t) // 印出最短路徑 { for (int i=s; i!=t; i=next[i][t]) cout << i; cout << t; }

中繼點順序

分類時，其實可以採用任意的中繼點順序。

舉例來說，把i點到j點的路線分成兩種：經過第8點、未經過第8點。接著兩種再各自細分為：經過第5點、未經過第5點。如此不斷細分下去，直到圖上每一點都用過為止。

也就是說，在k的迴圈當中，k值並非一定要從0跑到V-1。k值可以隨意變動，只要0到V-1的數字都剛好出現一次就行了。

演算法：偵測負環

除了使用Bellman–Ford algorithm的方式以外，另外還有個更直觀的檢查方法：

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

d[i][j]是由i點走到j點的最短路徑長度，d[i][i]則是由i點出外繞一圈回到i點的最短路徑長度。如果d[i][i]的長度是負值，就表示這條路徑就是負環、或者包含負環（以負環作為捷徑）。

只要檢查每個環的所有可能的起點i（窮舉圖上所有點），檢查d[i][i]的長度，就可以知道圖上有沒有負環。

UVa 104 125 423 436 534 544 567 10048 10099 10246 10342 10985 10987 ICPC 4524

用途

一張有向圖，找出所有兩點之間的最短路徑。

Johnson's algorithm首先重新調整邊的權重為非負數，順便檢查圖上是否有負環，接著放心的使用Dijkstra's algorithm計算所有兩點之間的最短路徑。

重新調整權重

如何調整權重，才不會影響最短路徑、負環的位置呢？

這裡介紹一個巧妙的方法：首先圖上每一個x點都設定一個權重h(x)，然後將一條由i點到j點的邊的權重w(i,j)，重新調整成w'(i,j) = w(i,j) + h(i) - h(j)。

一、一條路徑s⤳t，權重變成了：

  w'(s⤳t)
= w'(s→a→b→…→z→t)
= w'(s,a) + w'(a,b) + … + w'(z,t)
= [ w(s,a)+h(s)-h(a) ] + [ w(a,b)+h(a)-h(b) ] + … + [ w(z,t)+h(z)-h(t) ]
= w(s,a) + w(a,b) + … + w(z,t) + h(s) - h(t)
= w(s→a→b→…→z→t) + h(s) - h(t)
= w(s⤳t) + h(s) - h(t)

一加一減相消，得到簡潔的結果。

h(s)和h(t)都是定值。由s點到t點的每一條路徑，權重的變動量都一樣，權重大小關係保持不變，於是乎由s點到t點的最短路徑保持不變。圖上的最短路徑，調整權重之後，依然保持不變。

二、一個環s⤳s，權重變成了：

  w'(s⤳s)
= w'(s→a→b→…→s)
= w(s→a→b→…→s) + h(s) - h(s)
= w(s⤳s)

環的權重保持不變，於是乎由s點到s點的負環保持不變。圖上的負環，調整權重之後，依然保持不變。

重新調整權重為非負數：利用單源最短路徑長度

調整權重而不會影響最短路徑和負環的方法已經有了。現在要妥善設定h(x)的值，讓每一條邊的權重都調整為非負數。

找到最短路徑樹之後，圖上每一條邊都不可能再做relaxation，數學式子d(i) + w(i,j) ≥ d(j)，移項w(i,j) + d(i) - d(j) ≥ 0，正好就是調整權重的式子。

因此，令h(x)是由一個起點到各個x點的最短路徑長度，就能重新調整權重為非負數；無論起點是哪一點，數學式子都會成立。

起點應該選誰呢？因為圖上每一條邊都必須調整權重、圖上每一個點都必須設定h(x)值，所以起點必須能夠到達圖上每一個點，如此圖上每一個點才有h(x)值。

巧妙的解決方式：增加一個超級起點，連向圖上每一個點，權重設定為零。

順帶一提，以單源最短路徑長度重新調整權重，所有最短路徑的所有邊，權重都會變成零。這是一個很好用的特性。

演算法

一、增加一個超級起點，連向原圖每一個點，權重設定為零。
二、以超級起點作為起點，實施Bellman–Ford algorithm。
　甲、求得超級起點到原圖每一個點的最短路徑長度，作為h(x)。
　乙、順便檢查原圖是否有負環。
三、調整原圖每一條邊(i,j)的權重：
　　w'(i,j) = w(i,j) + h(i) - h(j)
四、原圖每一個點分別作為起點，
　　分別實施Dijkstra's algorithm with priority queue，
　　找出圖上任兩點之間的最短路徑。
五、找出最短路徑後，對照原圖求出正確的最短路徑長度。
　　或者利用h(x)逆推：w(s⤳t) = w'(s⤳t) - h(s) + h(t)。

時間複雜度

一次Bellman–Ford algorithm以及V次Dijkstra's algorithm with priority queue的時間。

圖的資料結構為adjacency lists是O(V² + VElogV)。當圖上的邊很少，比Floyd–Warshall algorithm來得快。

用途

一張有向圖，選定一個起點與一個終點，找出起點到終點的最短路徑。

single source shortest paths的label setting algorithm

實施單源最短路徑演算法，一旦遇到終點就馬上停止。比起點到終點還要長的最短路徑，得以略過計算，節省時間。

無法抵達終點的最短路徑，能不能也略過計算呢？

state space tree的A* search

請見本站文件「state space tree」。

運用估計函數h(x)，容易直奔終點，解決了方才的問題。

二維平面上的最短路徑，可以用「當前點到終點的直線距離」作為估計函數h(x)。一般的圖的最短路徑，沒有規律可循，無法估計距離。

時間複雜度

儘管label setting algorithm與A* search的時間複雜度相同，但是A* search容易直奔終點、計算時間較少。現行的時間複雜度標記方式，無法明確區分兩者的快慢差異。

估計函數用來改變遍歷順序

估計函數h(x)用來改變遍歷順序。一個估計函數，如同一個排列函數（permutation），重新排列所有點，得到一個點順序（vertex ordering）。

權重函數、成本函數，功效相同。

label setting algorithm使用權重函數w(i,j)、uniform-cost search使用成本函數g(x)，兩者的遍歷順序完全相同！

  argmin { d(s⤳i) + w(i,j) }   label setting algorithm
     ʲ                         尋找不在樹上、離起點最近的點
= argmin { d(s⤳j) }
     ʲ
= argmin { g(j) }              uniform-cost search
     ʲ                         尋找成本最小的點

調整函數、估計函數，功效相同。

label setting algorithm引入調整函數-h(x)讓權重變成w(i,j) - h(i) + h(j)、A* search引入估計函數h(x)讓成本變成g(x) + h(x)，兩者的遍歷順序完全相同！

  argmin { d'(s⤳i) + w'(i,j) }      label setting algorithm with reweighting
= argmin { d(s⤳i) - h(s) + h(i) + w(i,j) - h(i) + h(j) }
= argmin { d(s⤳i) + w(i,j) + h(j) - h(s) }
= argmin { d(s⤳j) + h(j) - h(s) }
= argmin { g(j) + h(j) - h(s) }
= argmin { g(j) + h(j) } - h(s)     h(s)是定值，不影響最小值位置
= argmin { g(j) + h(j) }            A* search

label setting algorithm with reweighting = A* search

我們可以堂堂正正回到圖論領域。我們可以直接使用label setting algorithm的一系列演算法了！

運用調整函數-h(x)，改變遍歷順序，容易直奔終點！

這是個專利

此演算法是Microsoft的專利。照理來說，我不可以介紹。

說文解字

ALT是指A* search、landmark、triangle inequality。

triangle inequality：利用單源最短路徑長度，調整權重為非負數。
landmark：單源最短路徑的起點。
A* search：遍歷時容易直奔地標。

調整函數：單源最短路徑長度

d⁺(x)和-d⁻(x)都可以重新調整權重為非負數。

令d⁺(x)是由一個起點a到各個x點的最短路徑長度。最短路徑之三角不等式d⁺(i) + w(i,j) ≥ d⁺(j)，移項w(i,j) + d⁺(i) - d⁺(j) ≥ 0。因此w'(i,j) = w(i,j) + d⁺(i) - d⁺(j)可以重新調整權重為非負數。

令d⁻(x)是由各個x點到一個終點a的最短路徑長度。最短路徑之三角不等式w(i,j) + d⁻(j) ≥ d⁻(i)，移項w(i,j) - d⁻(i) + d⁻(j) ≥ 0。因此w'(i,j) = w(i,j) + (-d⁻(i)) - (-d⁻(j))可以重新調整權重為非負數。

估計函數：單源最短路徑長度

令d⁺(x)是由a點到各個x點的最短路徑長度。最短路徑之三角不等式d⁺(x) + d(x⤳t) ≥ d⁺(t)，移項d(x⤳t) ≥ -d⁺(x) + d⁺(t)。因此h(x) = -d⁺(x) + d⁺(t)可以當作估計函數、-h(x)可以重新調整權重為非負數。

令d⁻(x)是由各個x點到a點的最短路徑長度。最短路徑之三角不等式d(x,t) + d⁻(t) ≥ d⁻(x)，移項d(x,t) ≥ d⁻(x) - d⁻(t)。因此h(x) = d⁻(x) - d⁻(t)可以當作估計函數、-h(x)可以重新調整權重為非負數。

合併調整函數

兩個調整函數h₁(x)與h₂(x)一旦能夠調整權重為非負數，兩者的最大值max(h₁(x), h₂(x))也能夠調整權重為非負數。最小值亦然。

{ w(i,j) + h₁(i) - h₁(j) ≥ 0
{ w(i,j) + h₂(i) - h₂(j) ≥ 0
max( w(i,j), w(i,j) ) + max( h₁(i), h₂(i) ) - max( h₁(j), h₂(j) ) ≥ 0
w(i,j) + max( h₁(i), h₂(i) ) - max( h₁(j), h₂(j) ) ≥ 0

取最大值的好處，以估計函數的立場來看，就是估計更加精準，仍舊不高估。

按照本站行文風格，我應該講最小上界與最大下界，不過我想最大值與最小值比較好懂吧。

演算法

一、建立超級起點，調整權重為非負數。
　（調整權重為非負數，以便實施高速演算法。）
二、選擇數個地標，調整權重為非負數。
　（調整權重，即是調整遍歷順序，以便直奔地標。）
　甲、選擇數個地標。
　乙、分別計算單源最短路徑長度。
　　（調整權重為非負數，以便取最大值。）
　　（順帶一提，取最小值，即是一齊計算多源最短路徑。）
　丙、取最大值，合併成一個調整函數。
三、點到點最短路徑：label setting algorithm系列。

選擇地標

如何選擇地標，目前還沒有定論。地標均勻分布、地標呈蜘蛛網狀散開、地標兩兩相距最遠、地標放在主幹道上宛如收費站、地標放在交通要衝四通八達之處、地標放在經常路過的地方、……。

一邊更新地標、一邊計算最短路徑，這樣又可以發幾篇論文了。

最短距離的下限與上限

估計函數h(x)負責下限，reach函數r(x)負責上限。

d(i⤳j)最短距離的下限：max( -d⁺(i) + d⁺(j), d⁻(i) - d⁻(j) )
d(i⤳j)最短距離的上限：min { max d⁻(x) + max d⁺(x) } = min { r⁻(x) + r⁺(x) }
                      max { min d⁻(x) + min d⁺(x) }

加速技巧：reach

抵達x點的所有最短路徑的長度最大值。一旦超過最大值，就不必relaxation。計算過程當中，最短路徑長度只增不減，一旦超過最大值，甚至可以直接丟掉x點。離開x點亦然。

r⁻(x) = max d(i⤳x)
         i
r⁺(x) = max d(x⤳j)
         j

if d(s⤳i) + w(i,j) ≤ r⁻(j) and h(j⤳t) ≤ r⁺(j) then relaxtion

前後兩段路徑可能共用路徑，導致效果變差。改為窮舉穿過x點的所有最短路徑，前後兩段路徑取長度最小值。

r(x) = max { min( d(i⤳x) , d(x⤳j) ) }
      shortest path i⤳x⤳j

if min( d(s⤳i) + w(i,j) , h(j⤳t) ) ≤ r(j) then relaxtion

加速技巧：shortcut

建立便道，降低reach。

加速技巧：transit node routing

一塊土地的出入口們，求得所有點對最短路徑。穿越土地，直接查表。

加速技巧：highway hierarchy / highway graph

收縮必經之路。遞迴下去。

加速技巧：contraction hierarchy

收縮冷門地點，改成便道。遞迴下去。

加速技巧：hub labelling

每個點的最短路徑樹，只存一部分。起點與終點，查表找到共同中繼點。

有向圖演算法

請先具備「matching」之知識。

利用最小權二分匹配，解決有向圖的點到點最短路徑問題。但是圖上不得有負環。

一、額外建立二分圖：
　點：X側、Y側都有V個點。
　邊：若原圖有一條i點到j點的有向邊，
　　　則二分圖就有一條Xi點到Yj點的邊。
二、轉化問題：
　口、增加Xi點到Yi點的邊，權重設為零。
　口、X側，去掉起點，也去掉連至起點的邊。
　口、Y側，去掉終點，去掉終點連出的邊。
三、計算最小權二分匹配。

一、額外建立二分圖：
　口、複製原圖的adjacency matrix。
二、轉化問題：
　口、對角線改為零。
　口、去除起點編號的column。
　口、去除終點編號的row。
　　　（最後成為(V-1)×(V-1)矩陣。）
三、計算最小權二分匹配。

無向圖演算法

利用最小權匹配，解決無向圖的點到點最短路徑問題。但是圖上不得有負環。

一、額外建立無向圖：
　點：V個原來的點，再加上V個複製的點。
　邊：若原圖有一條i點到j點的無向邊，
　　　則新圖就有：
　　　一條i 點到j 點的無向邊、
　　　一條i'點到j 點的無向邊、
　　　一條i 點到j'點的無向邊、
　　　一條i'點到j'點的無向邊。
二、轉化問題：
　口、增加i點到i'點的無向邊，權重設為零。
　口、去掉起點，也去掉連著該點的邊。
　口、去掉終點的複製點，也去掉連著該點的邊。
三、計算最小權匹配。