The Floyd-Warshall Algorithm

Floyd-Warshall演算法是用來計算all-pairs的最短路徑，
考慮的是從vertex i直接到vertex j的距離，
以及vertex i經過一些中介點vertex k到vertex j的距離，
去判斷哪個距離比較短。

用d_ij^(k)表示從vertex i到vertex j的最短路徑距離，
而所有中介點都在set {1,2,...,k} 之內。
之後要計算矩陣D⁽¹⁾、D⁽²⁾、...D⁽ⁿ⁾，
最後D⁽ⁿ⁾ = (d_ij⁽ⁿ⁾)可以得到最終答案：d_ij⁽ⁿ⁾ = δ(i,j) for all i,j∈V

而最後為了印出shortest path，
我們還必須記錄每個點的祖先(predecessor)。

定義π_ij^(k)為vertex j的祖先，
其中vertex i經過一些中介點抵達vertex j為最短路徑，
而所有中介點都在set {1,2,...,k} 之內，
之後要計算矩陣Π⁽¹⁾、Π⁽²⁾、...、Π⁽ⁿ⁾。

簡單來講，
就是每當D^(k)(i,j)有改變時，就更新Π^(k)(i,j)為Π^(k-1)(k,j)。

（註：在本篇文章中，我使用D^(k)(i,j)代表課本的d_ij^(k)、Π^(k)(i,j)代表課本的π_ij^(k)）

Introduction to Algorithms Fig.25.1 & Fig. 25.4

用往前查表的方式填矩陣。(dynamic programming)

k為中介點
D^(k)(i,j) = min {D^(k-1)(i,j)，D^(k-1)(i,k) + D^(k-1)(k,j)}
                   直接去          先經過k再去
                   (i->j)         (i->k->j)

例：
D⁽¹⁾(4,5)
= min {D⁽⁰⁾(4,5)，D⁽⁰⁾(4,1) + D⁽⁰⁾(1,5)}
= min {∞，-2} = -2
因為D⁽¹⁾(4,5) ≠ D⁽⁰⁾(4,5)，
所以要更新Π⁽¹⁾(4,5) = Π⁽⁰⁾(1,5) = 1

例：
D⁽³⁾(4,2)
= min {D⁽²⁾(4,2)，D⁽²⁾(4,3) + D⁽²⁾(3,2)}
= min {5，-1} = -1
更新Π⁽³⁾(4,2) = Π⁽²⁾(3,2) = 3

例：
D⁽⁵⁾(1,3)
= min {D⁽⁴⁾(1,3)，D⁽⁴⁾(1,5) + D⁽⁴⁾(5,3)}
= min {-1，-3} = -3
更新Π⁽⁵⁾(1,3) = Π⁽⁴⁾(5,3) = 4


※Floyd-Warshall演算法的應用：Transitive Closure of a Directed Graph