主題
Search

Floyd-Warshall 演算法

下載 Mathematica Notebook下載 Wolfram Notebook

Floyd-Warshall 演算法，也被稱為 Floyd 演算法、Roy-Floyd 演算法、Roy-Warshall 演算法或 WFI 演算法，是一種用於高效且同時找到加權（且可能是定向）圖中每對頂點之間最短路徑（即，圖測地線）的演算法。

Floyd 演算法本質上等同於 Roy (1959) 和 Warshall (1962) (Pemmaraju 和 Skiena 2003) 獨立發現的傳遞閉包演算法，這也是它與這三位作者相關聯的原因。

在電視劇犯罪劇集 NUMB3RS 第 4 季“黑天鵝”一集中，數學天才 Charles Eppes 提議使用 Floyd-Warshall 演算法來分析一名炸彈嫌疑人最近的目的地。

另請參閱

所有點對最短路徑, Bellman-Ford 演算法, Dijkstra 演算法, 圖距離, 圖距離矩陣, 圖測地線, 最短路徑問題

使用 探索

參考文獻

Atallah, M. J. (編). "Basic Graph Algorithms." Algorithms and Theory of Computation Handbook 第 6 章. Boca Raton, FL: CRC Press, 1998.Floyd, R. W. "Algorithm 97." Comm. ACM 5-6, 345, 1962.Larson, R. 和 Odoni, A. "Shortest Paths between All Pairs of Nodes." Urban Operations Research §6.2.2. 1981. http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html.Loerch, U. "Floyd's Algorithm." 奧克蘭，紐西蘭: 奧克蘭大學計算機科學系, 2000. http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node21.html.Pemmaraju, S. 和 Skiena, S. "All-Pairs Shortest Paths" 和 "Transitive Closure and Reduction." Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica §8.1.2 §8.5.2. 劍橋，英格蘭: 劍橋大學出版社, pp. 330-331 和 353-356, 2003.Preiss, B. "Floyd's Algorithm." Data Structures and Algorithms with Object-Oriented Design Patterns in Java. 1998. http://www.brpreiss.com/books/opus5/html/page570.html.Roy, B. "Transitivité et connexité." C. R. Acad. Sci. Paris 249, 216-218, 1959.Warshall, S. "A Theorem on Boolean Matrices." J. ACM 9, 11-12, 1962.

在 中被引用

Floyd-Warshall 演算法

請按如下方式引用

Weisstein, Eric W. "Floyd-Warshall 演算法。" 來自 Web 資源。 https://mathworld.tw/Floyd-WarshallAlgorithm.html

主題分類