介绍
它旨在找出从每个顶点v到每个u的最短路径。显式存储所有路径的确确实会占用大量内存, 因为每个顶点都需要一个生成树。对于内存消耗, 这通常是不切实际的, 因此通常将这些问题视为所有对-最短距离问题, 其目的是仅找到每个节点到每个节点到另一个节点的距离。我们通常希望以表格形式输出：u行和v列中的条目应为从u到v的最短路径的权重。
三种改进方法：
| 算法 | 成本 |
|---|---|
| 矩阵乘法 | O (V3 logV) |
| Floyd-Warshall | O (V3) |
| 约翰逊 | （V2 log？V + VE） |
文章图片
推荐阅读
- 图论算法（Floyd-Warshall算法）
- 有向无环图中的单源最短路径
- 最短路径（ellman-Ford算法）
- 图论算法（Dijkstra算法）
- 图论（松弛技术）
- 图论（最短路径的表示）
- 图论（负权重边）
- 图论（单源最短路径）
- DNS问题故障排除（使用nslookup、dig和host等命令）