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

问题描述

如果你有一个图，并需要找到它的直径（也就是两个节点之间的最大距离），你怎么能做到这一点在 O（日志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?

或显示一个伪code？

Or show a pseudocode?

推荐答案

对于一般的图形 G =（V，E）没有为O（log V *（V + E））时间复杂度闻名计算口径的算法。 目前最好的解决办法就是 O（V * V * V），例如，通过计算所有最短路径与弗洛伊德沃肖尔的算法。 对于稀疏图，即当电子在 O（N * N），约翰逊的算法为您提供了与 O（V * V *日志（V）+ V * E）一个更好的时间复杂度。

For a general Graph G=(V,E) there is no O(log V * (V + E)) time complexity algorithm known for computing the diameter. The current best solution is O(V*V*V), e.g., by computing all shortest Paths with Floyd Warshall's Algorithm. For sparse Graphs, i.e. when E is in o(N*N), Johnson's Algorithm gives you with O(V*V*log(V)+V*E) a better time complexity.

如果你的图具有一定的属性，如无环（树），您可以得到更好的。

If your graph has certain properties like acyclic (Tree) you can get better.

所以，坏消息是，在Dijkstra算法是不够的，在一般的情况下...

So the bad news is, the Dijkstra won't be enough in the general case...

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