图形直径的算法? [英] Algorithm for diameter of graph?

问题描述

如果你有一个图，需要求它的直径(两个节点之间的最大距离)，你怎么做O(log v * (v + e))复杂性.

If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity.

维基百科说你可以使用 Dijkstra 算法 带有 二元堆.但我不明白这是如何工作的.谁能解释一下?

Wikipedia says you can do this using Dijkstra's algorithm with a binary heap. But I don't understand how this works. Can someone explain please?

或者显示伪代码?

推荐答案

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

I know I'm a year late to the thread, but I don't believe any of these answers are correct. OP mentioned in the comments that the edges are unweighted; in this case, the best algorithm runs in O(n^ω log n) time (where ω is the exponent for matrix multiplication; currently upper bounded at 2.373 by Virginia Williams).

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

The algorithm exploits the following property of unweighted graphs. Let A be the adjacency matrix of the graph with an added self-loop for each node. Then (A^k)_ij is nonzero iff d(i, j) ≤ k. We can use this fact to find the graph diameter by computing log n values of A^k.

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

Here's how the algorithm works: let A be the adjacency matrix of the graph with an added self loop for each node. Set M₀ = A. While M_k contains at least one zero, compute 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.

Eventually, you find a matrix M_K with all nonzero entries. We know that K ≤ log n by the property discussed above; therefore, we have performed matrix multiplication only O(log n) times so far. We can now continue by binary searching between M_K = A^2K and M_K-1 = A^2K-1. Set B = M_K-1 as follows.

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

Set DIAMETER = 2^k-1. For i = (K-2 ... 0), perform the following test:

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

Multiply B by M_i and check the resulting matrix for zeroes. If we find any zeroes, then set B to this matrix product, and add 2ⁱ to DIAMETER. Otherwise, do nothing.

最后，返回直径.

作为一个次要的实现细节，可能有必要在每次矩阵乘法之后将矩阵中的所有非零项设置为 1，这样值就不会变得太大和笨拙而无法用少量写下来时间.

As a minor implementation detail, it might be necessary to set all nonzero entries in a matrix to 1 after each matrix multiplication is performed, so that the values don't get too large and unwieldy to write down in a small amount of time.

这篇关于图形直径的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！