图论算法:全对最短路径

介绍

它旨在找出从每个顶点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), 其中

全对最短路径
微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?