图的直径算法？

Question

如果你有一个图形,并且需要找到它的直径(这是两个节点之间的最大距离),你怎么能在O(log v * (v + e))复杂性上做到这一点.

维基百科说,你可以用这个做Dijkstra's algorithm了binary heap.但我不明白这是如何工作的.有人可以解释一下吗？

或者显示伪代码？

Answer 1

对于一般图表G=(V,E),没有O(log V * (V + E))已知用于计算直径的时间复杂度算法.目前最好的解决方案是O(V*V*V),例如,通过使用Floyd Warshall算法计算所有最短路径.对于稀疏图,即当E是o(N*N),约翰逊的算法为您提供了O(V*V*log(V)+V*E)一个更好的时间复杂度.

如果您的图表具有某些属性,如非循环(树),您可以变得更好.

所以坏消息是,Dijkstra在一般情况下还不够......

Answer 2

我知道我已经迟到了一年，但是我不相信这些答案中的任何一个都是正确的。OP在评论中提到边缘未加权；在这种情况下，最佳算法的运行时间为$ O（n ^ {\ omega}）\ log n $时间（其中$ \ omega $是矩阵乘法的指数；目前，弗吉尼亚·威廉姆斯的上限为$ 2.373 $）。

该算法利用了未加权图的以下属性。令$ A $为图的邻接矩阵，并为每个节点添加一个自环。那么$（A ^ k）_ {ij} $是非零的iff $ d（i，j）\ le k $。我们可以通过计算$ \ log n $的值$ A ^ k $来利用该事实找到图形直径。

算法的工作原理如下：令$ A $为图的邻接矩阵，并为每个节点添加一个自环。设置$ M_0 = A $。$ M_k $至少包含一个零，请计算$ M_ {k + 1} = M_ {k} ^ 2 $。

最终，您找到具有所有非零条目的矩阵$ M_ {K} $。我们知道$ K \ le \ log n $由上面讨论的属性组成；因此，到目前为止，我们仅执行了$ O（\ log n）$次矩阵乘法。现在，我们可以继续在$ M_ {K} = A ^ {2 ^ K} $和$ M_ {K-1} = A ^ {2 ^ {K-1}} $之间进行二进制搜索。如下设置$ B = M_ {K-1} $。

设置DIAMETER = $ 2 ^ {k-1} $。对于$ i =（K-2 \ dots 0）$，执行以下测试：

将$ B $乘以$ M_ {i} $，然后检查所得矩阵是否为零。如果找到零，则将$ B $设置到此矩阵乘积，并将$ 2 ^ i $添加到DIAMETER。否则，什么都不做。

最后，返回DIAMETER。

作为一个次要的实现细节，在执行每个矩阵乘法之后，可能有必要将矩阵中的所有非零条目设置为$ 1 $，以使值不会变得太大和笨拙以至于无法在短时间内写下。