所有对最短路径

引言

它的目标是找出从每个顶点 v 到其他所有顶点 u 的最短路径。 显式地存储所有路径实际上可能非常耗费内存，因为我们需要为每个顶点生成一个生成树。 这在内存消耗方面通常是不切实际的，因此这些通常被认为是所有对最短距离问题，其目标是找到从一个节点到另一个节点的距离。 我们通常希望输出以表格形式显示：u 的行和 v 的列中的条目应为从 u 到 v 的最短路径的权重。

三种改进方法

与假设图的邻接表表示的单源算法不同，大多数算法都使用邻接矩阵表示。 （Johnson 算法用于稀疏图，使用邻接表。）输入是一个 n x n 矩阵 W，表示 n 顶点有向图 G = (V, E) 的边权重。 也就是说，W = (w_ij)，其中