图论算法：全对最短路径

介绍

它旨在找出从每个顶点v到每个u的最短路径。显式存储所有路径的确确实会占用大量内存, 因为每个顶点都需要一个生成树。对于内存消耗, 这通常是不切实际的, 因此通常将这些问题视为所有对-最短距离问题, 其目的是仅找到每个节点到每个节点到另一个节点的距离。我们通常希望以表格形式输出：u行和v列中的条目应为从u到v的最短路径的权重。

三种改进方法：

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