16

如果你有一个图，并且需要找到它的直径（即两个节点之间的最大距离），你怎么能做的很O(log v * (v + e))复杂。

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

或者显示一个伪代码？

4

10 回答 10

13

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

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

以下是该算法的工作原理：设 A 是图的邻接矩阵，每个节点都添加了自循环。设置 M 0 = A。当 M k包含至少一个零时，计算 M k+1 = M k 2。

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

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

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

最后，返回直径。

作为一个次要的实现细节，在执行每个矩阵乘法之后，可能需要将矩阵中的所有非零条目设置为 1，这样这些值就不会变得太大且难以在短时间内写下来。

于 2015-01-23T13:28:44.473 回答
10

对于一般 Graph 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 在一般情况下是不够的......

于 2013-03-27T08:26:47.620 回答
1

正如 eci 所提到的，其中一种解决方案是使用 Floyd-Warshall 算法。如果您需要它的代码，可以在此处找到它的 C++ 版本。

于 2014-04-16T05:42:39.133 回答
1

Boost BGL 有一个名为“rcm_queue”的小型扩展双端队列类，可以通过简单的广度优先搜索找到顶点的偏心率，这意味着 O(E) 的复杂性。

http://www.boost.org/doc/libs/1_54_0/boost/graph/detail/sparse_ordering.hpp

由于可以通过遍历所有顶点的偏心率来计算直径，因此可以计算复杂度为 O(V*E) 的图的直径。

特别是对于一个 deg(G) <<< V 非常稀疏的图，我没有找到任何运行时间更好的东西。

我没有研究 Floyd Warshall 算法。我只是在处理一个具有 > 5.000.000 个顶点但任何顶点的最高度数小于 15 的图，我认为，这可能会优于具有 V*V*log(V) 复杂度的算法。

编辑

当然，这仅适用于无向图而不是负加权（甚至仅未加权？我不确定 atm）

于 2013-10-03T19:30:31.833 回答
1

图描述——无向无权，n个节点，m条边对于图的直径，我们需要计算所有节点对之间的最短路径。源节点到所有其他节点之间的最短路径可以使用 BFS 算法计算无向和未加权图。1 个节点的时间复杂度为O(n + m)。在这里，由于我们需要对 n 个节点进行 BFS，因此在所有节点对之间找到最短路径的总时间复杂度变为O(n(n + m))。由于有n(n-1)/2对节点，所以我们有n(n-1)/2所有节点之间的最短路径的值。对于直径，我们需要获得这些值的最大值，也就是 O(n*n)。所以最终的时间复杂度变为：

       O(n(n + m)) + O(n*n) = O(n(2n + m)) = O(n(n + m))

用于获取所有节点对之间最短路径的伪代码。我们使用一个名为 Shortest_paths 的矩阵来存储任意两对节点之间的最短路径。我们正在使用一个名为 flag 的字典，其值为 true 或 false ，指示顶点是否已被访问。对于 BFS 的每次迭代，我们将这个字典初始化为全为 false。我们使用队列 Q 来执行 BFS。算法 BFS（适用于所有节点）

Initialize a matrix named Shortest_paths[n][n] to all -1. 
    For each source vertex s
        For each vertex v
            Flag[v] = false
        Q = empty Queue
        Flag[s] = true
        enQueue(Q,s)
        Shortest_paths[s][s] = 0
        While Queue is not empty
            Do v = Dequeue(Q)
            For each w adjacent to v
                Do if flag[w] = false
                    Flag[w] = true
                    Shortest_paths[s][w] = Shortest_paths[s][v] + 1
                    enQueue(Q,w) 
    Diameter = max(Shortest_paths)
    Return Diameter
于 2017-09-19T14:05:31.053 回答
1

假设图未加权，则以下步骤可以在 O(V * ( V + E )) 中找到解，其中 V 是顶点数，E 是边数。

让我们将 2 个顶点 u, v 之间的距离定义为 u 和 v 之间的最短路径的长度。用 d(u, v) 表示 定义顶点 v 的偏心率为 e(v) = max {d(u,五）| u ∈ V(G)} (V(G) 是图 G 中的顶点集) 定义 Diameter(G) = max{e(v) | v ∈ V(G)}

现在到算法：

1- 对于 V(G) 中的每个顶点 v 运行 BFS(v) 并构建从每个顶点到其他顶点的距离的二维数组。（计算每个顶点到其他顶点的距离在BFS 算法中很容易做到）

2- 计算步骤 1 中创建的二维数组中每个顶点的 e(v) 3- 通过从步骤 2 中找到最大 e(v) 来计算直径 (G)

现在分析这个算法，很容易看出它是由O（V *（V + E））的第一步主导的

在维基百科中阅读有关直径的这部分内容

另一种在线性时间 O(V + E) 中运行的算法 1- 在任意随机顶点 v ∈ V(G) 上运行 BFS 2- 选择距离最大的顶点 u 3- 在该顶点 u 上再次运行 BFS 4- 直径是从第 3 步生成的最大距离

于 2015-11-06T05:44:47.433 回答
0

首先，您需要找到图形的凸包（找到它是 O(nh)，其中 h 是 hull 上的节点数）。直径点将位于凸包上，因此问题将减少到在 h 个点中找到最远的点。因此，总订单将是 O(nh+h*h)。

于 2013-05-18T10:34:31.707 回答
0

实际上，如果图形非常大，您将需要使用 Dijkstra 算法来找到最短距离。所以这取决于 OP 的图有多少节点。

于 2013-12-04T21:59:58.183 回答
0

你不能一直单调地将 A 提高到下一个幂并跟踪哪些 (i,j) 有一些 A^k 的非零条目吗？一旦所有 i,j 在先前计算的 A^k 中都有一个非零值，无论你在什么 k 上都是图形的直径。

于 2022-01-05T18:50:26.427 回答
-1

这只能发生在未加权的图上。其中 bfs 给出了 o(v+e) 中的最短路径树，你对 v 源重复相同的操作。

于 2014-07-17T15:12:31.387 回答