图中每个顶点之间的距离

Question

是否有algo/efficient方法来计算图中每个顶点到所有其他顶点的距离。

与 Dijkstra 不同 - 我正在寻找一种方法来计算所有顶点到所有顶点（不是一个到所有）的距离。

谢谢！

Answer 1

如果 "distance" 是指 "shortest distance"，那么答案是 "Yes"。一种非常流行的全对最短路径算法是 Floyd Warshall Algorithm。实施起来非常容易：

for k = 0 ; k != N ; k++
    for i = 0 ; i != N ; i++
        for j = 0 ; j != N ; j++
            W[i,j] = MIN(W[i,j], W[i,k]+W[k,j])

但是，它不适用于大规模稀疏图，因为它使用邻接矩阵实现。它也不适用于具有负循环的图形，因为此类图形中的最短路径未定义。

Distance between every Vertices in Graph