介绍
它旨在找出从每个顶点v到每个u的最短路径。显式存储所有路径的确确实会占用大量内存, 因为每个顶点都需要一个生成树。对于内存消耗, 这通常是不切实际的, 因此通常将这些问题视为所有对-最短距离问题, 其目的是仅找到每个节点到每个节点到另一个节点的距离。我们通常希望以表格形式输出：u行和v列中的条目应为从u到v的最短路径的权重。
三种改进方法：
| 算法 | 成本 |
|---|---|
| 矩阵乘法 | O (V3 logV) |
| Floyd-Warshall | O (V3) |
| 约翰逊 | （V2 log？V + VE） |
与假设图的邻接列表表示的单源算法不同, 大多数算法使用邻接矩阵表示。 （稀疏图的约翰逊算法使用邻接表。）输入是一个n x n矩阵W, 表示n个顶点有向图的边权重G =（V, E）。也就是说, W =（wij）, 其中
