2016/12/9 Algorithm (Floyd-Warshall)

Ch25. All-Pairs Shortest Paths 結束
參考: http://www.csie.ntnu.edu.tw/~u91029/Path2.html

另從11:10開始有一堂助教講解 midterm考題

---
以下改寫自wikipedia:

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖中兩結點之間的最短路徑。算法具體的形式包括：(前三個是Single Source(ch24), 最後一個是All Pairs(ch25))

• 確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。適合使用Dijkstra算法。
• 確定終點的最短路徑問題 - 該問題等同於把所有路徑方向反轉的確定起點的問題。
• 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
• 全局(All Pairs)最短路徑問題 - 求圖中所有的最短路徑。適合使用Floyd-Warshall算法。

最常用的演算法有：

• Dijkstra算法  (Ch24.3)
• A*算法
• Bellman-Ford算法  (Ch24.1)
• SPFA算法（Bellman-Ford算法的改進版本）
• Floyd-Warshall算法  (Ch25.2)  Time: O(n^3) Space:O(n^2)

---
以下改寫自 http://www.csie.ntnu.edu.tw/~u91029/Path2.html和wikipedia:

Floyd-Warshall是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權（但不可存在負權迴路)的最短路徑問題。