Floyd–Warshall

定义 Definition

Floyd–Warshall（弗洛伊德–沃舍尔算法）：一种经典的图算法，用于在加权图中计算所有点对之间的最短路径（All-Pairs Shortest Paths, APSP）。它可以处理负权边，但通常要求不存在负权回路（否则最短路无意义）。常见时间复杂度为 **O(n³)**。

发音 Pronunciation (IPA)

/ˌflɔɪd ˈwɔːrʃɔːl/

例句 Examples

We used Floyd–Warshall to find the shortest paths between every pair of cities.
我们使用 Floyd–Warshall 算法来找到每一对城市之间的最短路径。

Although Dijkstra’s algorithm is faster for single-source queries, Floyd–Warshall is convenient when you need all-pairs shortest paths and can store the full distance matrix.
虽然 Dijkstra 算法在单源查询时更快，但当你需要所有点对最短路径并且能够存储完整距离矩阵时，Floyd–Warshall 更方便。

词源 Etymology

这是一个以人名命名的算法：与计算机科学家 Robert W. Floyd（罗伯特·弗洛伊德） 和 Stephen Warshall（斯蒂芬·沃舍尔） 的相关工作有关。该算法常被描述为一种基于动态规划的逐步“松弛/更新”方法，通过允许中间节点集合逐渐扩大来更新任意两点间最短距离。

相关词 Related Words

• Algorithm
• Dynamic
• Graph
• Dijkstra
• Bellman-Ford
• Shortest
• Path
• Matrix
• Complexity
• Transitive

文学与经典著作 Literary Works

• Thomas H. Cormen et al., Introduction to Algorithms（《算法导论》）：在“全源最短路径（All-Pairs Shortest Paths）”章节中系统介绍 Floyd–Warshall。
• Steven S. Skiena, The Algorithm Design Manual（《算法设计手册》）：在图算法与最短路相关部分提及并对比其适用场景。
• Robert W. Floyd, “Algorithm 97: Shortest Path” (1962)：与该算法命名密切相关的早期经典文献之一。