all pairs shortest paths: Floyd–Warshall algorithm

用途

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

演算法

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,三層迴圈填表格。逐次添加一個中繼點,更新所有路徑長度。

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

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

中繼點順序

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

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

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

演算法:偵測負環

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

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

all pairs shortest paths: Johnson's algorithm

用途

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

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來得快。

point-to-point shortest path: A* search

用途

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

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容易直奔終點、計算時間較少。現行的時間複雜度標記方式,無法明確區分兩者的快慢差異。

point-to-point shortest path: label setting algorithm with reweighting

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

估計函數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),改變遍歷順序,容易直奔終點!

point-to-point shortest path: Goldberg–Harrelson algorithm (ALT algorithm)🚧

這是個專利

此演算法是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

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

point-to-point shortest path: matching

有向圖演算法

請先具備「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'點的無向邊,權重設為零。
 口、去掉起點,也去掉連著該點的邊。
 口、去掉終點的複製點,也去掉連著該點的邊。
三、計算最小權匹配。