图直径的算法？

Question

如果你有一个图，并且需要找到它的直径(这是两个节点之间的最大距离)，你如何在 O(log v * (v + e)) 复杂性。

维基百科说你可以使用 Dijkstra's algorithm 来做到这一点使用二进制堆。 但我不明白这是怎么回事。有人可以解释一下吗？

或者显示一个伪代码？

Answer 1

我知道我迟到了一年，但我不认为这些答案是正确的。 OP在评论中提到边缘未加权；在这种情况下，最佳算法的运行时间为 O(n^ω log n)(其中 ω 是矩阵乘法的指数；目前 Virginia Williams 的上限为 2.373)。

该算法利用了未加权图的以下属性。设 A 是图的邻接矩阵，每个节点都添加了自循环。那么 (A^k)_ij 是非零的当且仅当 d(i, j) ≤ k。我们可以使用这个事实通过计算 A^k 的 log n 值来找到图形直径。

算法的工作原理如下:设 A 为图的邻接矩阵，并为每个节点添加了自循环。设 M₀ = A。当 M_k 包含至少一个零时，计算 M_k+1 = M_k².

最终，您会找到一个包含所有非零元素的矩阵 M_K。根据上面讨论的性质，我们知道 K ≤ log n；因此，到目前为止，我们只执行了 O(log n) 次矩阵乘法。我们现在可以继续在 M_K = A^2K 和 M_K-1 = A< 之间进行二分查找sup>2^K-1。设 B = M_K-1 如下。

设置直径 = 2^k-1。对于 i = (K-2 ... 0)，执行以下测试:

将 B 乘以 M_i 并检查结果矩阵是否为零。如果我们找到任何零，则将 B 设置为该矩阵乘积，并将 2ⁱ 添加到 DIAMETER。否则，什么也不做。

最后，返回DIAMETER。

作为一个次要的实现细节，可能有必要在每次执行矩阵乘法后将矩阵中的所有非零元素设置为 1，这样值就不会变得太大而难以写下少量的时间。