有瑕

隨機客的 naïve algorithm for all-pairs shortest path based on Bellman-Ford 有瑕疵！投影片上如是說：

• Run Bellman-Ford to detect negative cycle in O(mn) time. If there are negative cycles, then stop.
• For each node i of the input graph G:
  Run Bellman-Ford in O(mn) time to compute d(i, j) for all nodes j.
• The overall time complexity is O(mn²), which could be Θ(n⁴) in the worst case.

問題在第一個步驟。Bellman-Ford 是 "single-source" shortest path 的演算法，那要如何決定起點呢？任意挑選不可行，反例如下：

這個圖中間有個 negative cycle，由三個點構成。如果隨便選卻沒選到那三個點之中的一個，那就找不到 negative cycle。可以想像，那三隻延伸出去的手臂可以相當長，而使選中那三個點的機率要多低有多低。解法很簡單：把第一個步驟拿掉就好了。對每個點召喚 Bellman-Ford 時，都做第 n 個 iteration 確定沒有 negative cycle。這樣對整體演算法的時間複雜度沒有影響，也對原本投影片上第二個步驟的敘述沒有嚴重影響 XD。如果要寫得詳細一點，就是

• For each node i of the input graph G:
  Run Bellman-Ford in O(mn) time to compute d(i, j) for all nodes j. If a negative cycle is detected, then stop.

不過加速部份的 preprocessing 那裡也有同樣問題，我還不知道可不可以省略，因為還沒聽完 XD。

--
難得有問題可以問 XD。

---

以下是針對 dynamic programming 的兩個演算法。首先，那個 negative cycle 的檢查很重要，因為後面的 recurrence relations 都假設 d 存在。（後註：課本講 Floyd-Warshall 演算法的時候直接假設沒有 negative cycles，很滑頭 XD。）不過，或許可以像 Bellman-Ford 一樣多做一次，若又有變動則代表有 negative cycle(s)。（這個想法有待證明或否證。）至於 Johnson 的 reweighting algorithm…還沒到那裡 XD。

--
或許是找助教或老師的時候了 XD。

---

聽完 Johnson 的演算法，或許那一次檢查 negative cycle 的 Bellman-Ford 可以用 0 號節點當起點？！（後註：課本正是這麼做 XD。）如果本來的圖沒有 negative cycle，新的圖也不會有 negative cycle；如果本來的圖有 negative cycle，那個 cycle 一定可以從 0 號節點抵達，那就會被 Bellman-Ford 找到。這樣的時間複雜度是 O((m + n - 1)(n + 1)) = O(mn + n²)，三個加速演算法都可以負擔。

所以隨機客（和課本）有個地方可以寫得更清楚一些：

• The node weight function h can be obtained by Bellman-Ford in O(mn) time.

這裡的 m 和 n 應該是指原圖的邊數和點數，但 Bellman-Ford 是以「加入 0 號點的圖」為輸入，所以時間複雜度挑剔一點的話不只是 O(mn)，而是 O(mn + n²)。不過對於「正常」的圖（m = Ω(n)），後者就可寫成 O(mn)。

--
這樣問題應該差不多解掉了吧 XD。