全部頂點對最短路徑 (All Pairs Shortest Paths)

A1(3,2) = min { A0(3,2) ， A0(3,1) + A0(1,2) } = min {∞，7}
A1(2,3) = min { A0(2,3) ， A0(2,1) + A0(1,3) } = min {2 ， 6+11}

使用的是 dynamic programming 策略，
就是採用建構式的方法：先建出 A0→ 再建出A1→ ... →An

其中 A0 就是最原始的 cost 矩陣。而 A1 則表示中間點可以經過 節點1
而 A2 則表示中間點可以經過 節點1 ~ 節點2

for i=1 to n
 for j=1 to n
   a[i,j] = cost[i,j];   /* 先把 cost 抄到 A0 之中*/

/* k 放最外面，控制可用的中間點，逐一建構 A0→A1→ ... →An  */
for k=1 to n
{ for i=1 to n              O(n^3)
 { for j=1 to n
   {
     /* 引入 k 當中間點，如果比較近，就改用這條路*/
     if ( a[i,j] > a[i, k] + a[k, j] )
       a[i,j] = a[i, k] + a[k, j];
   }
 }
}

重點提示：

1. 在 A2 的圖中， (i,j) 項的值怎麼算?

不要忘記，A2 的資料是由 A1 為藍本建構而來。
A2(i,j) = min { 原本 A1(i,j) , A1(i,2) + A1(2,j) }
在 A2 中，開放使用節點2，所以要考量，當選擇節點2為中繼時，是否較短路徑。

2. 複雜度與迴圈的設計為何?

迴圈用了 O(n^3) 而最外的計數器是 k 表是當前在建構 Ak 矩陣，
所謂 Ak 矩陣表示目前「中繼節點可用 A1~Ak」
而建構方式是由 A0→A1→...→An 所以 k 會放最外面。

3. 考試的速解法

解題時 A3 矩陣的 (2,1) 欄資料來源會是 (2,3) + (3,1)
不要再傻傻一個一個算了。