主题
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 算法, 图距离, 图距离矩阵, 图测地线, 最短路径问题

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

Floyd-Warshall 算法

请按如下方式引用

Weisstein, Eric W. "Floyd-Warshall 算法。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Floyd-WarshallAlgorithm.html

主题分类