图中每个顶点之间的距离

Question

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

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

谢谢！

Answer 1

如果“距离”是指“最短距离”，那么答案是“是”。一种非常流行的全对最短路径算法是Floyd Warshall 算法。它非常容易实现：

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])

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

Answer 2

我实际上设法导出了节点之间（最短）距离的解析表达式，您可以在这里找到：

https://www.researchgate.net/publication/379118066_Exact_analytic_expressions_for_discrete_first-passage_time_probability_distributions_in_Markov_networks