好的算法查找（稀疏）图的直径？ [英] Good algorithm for finding the diameter of a (sparse) graph?

问题描述

我有一个大，连接，稀疏图在邻接表的形式。我想找到两个顶点是，远越好，也就是说，图表和两个顶点的直径实现了。

I have a large, connected, sparse graph in adjacency-list form. I would like to find two vertices that are as far apart as possible, that is, the diameter of the graph and two vertices achieving it.

我在两个无向和有向箱子感兴趣此问题，对于不同的应用。在定向的情况下，我当然关心执导的距离（最短定向路径从一个顶点到另一个）。

I am interested in this problem in both the undirected and directed cases, for different applications. In the directed case, I of course care about directed distance (the shortest directed path from one vertex to another).

有没有比计算全对的更好的方法最短路径？

修改的：通过相距甚远越好，我当然指的是最长最短路径 - 即，最高在所有对的最短距离的顶点从一到其他

Edit: By "as far apart as possible", I of course mean the "longest shortest path" -- that is, the maximum over all pairs of vertices of the shortest distance from one to the other.

推荐答案

嗯，我已经把思想对这个问题一点点，有点谷歌搜索的，我很抱歉，但我无法找到任何算法似乎，它是只是找到所有对最短路径。

Well, I've put a little bit of thought on the problem, and a bit of googling, and I'm sorry, but I can't find any algorithm that doesn't seem to be "just find all pairs shortest path".

不过，如果你认为弗洛伊德 - 沃肖尔是唯一的算法计算（中大的Theta | V | ^ 3），这样的事情，那么我有一点好消息告诉你：约翰逊的算法稀疏图（ ！谢谢你，值得信赖CLRS）计算所有对最短路径（大哦（| V | ^ 2 * LGV + VE）），这应该是渐进更快稀疏图

However, if you assume that Floyd-Warshall is the only algorithm for computing such a thing (Big-Theta of |V|^3), then I have a bit of good news for you: Johnson's Algorithm for Sparse Graphs (thank you, trusty CLRS!) computes all pairs shortest paths in (Big-Oh (|V|^2 * lgV + VE)), which should be asymptotically faster for sparse graphs.

维基百科说，它适用于定向（不知道无向，但至少我想不出有任何理由为什么不），这里的的链接。

Wikipedia says it works for directed (not sure about undirected, but at least I can't think of a reason why not), here's the link.

还有什么关于可能是有用的图表？如果它可以很容易地映射到一个二维平面（因此，它的平面和边权服从三角不等式[它可能需要满足更严格的要求，我不知道]），你也许能够打破一些几何算法（凸包可以在nlogn运行，并找到最远点对很容易从那里）。

Is there anything else about the graph that may be useful? If it can be mapped easily onto a 2D plane (so, its planar and the edge weights obey the triangle inequality [it may need to satisfy a stricter requirement, I'm not sure]) you may be able to break out some geometric algorithms (convex-hull can run in nlogn, and finding the farthest pair of points is easy from there).

希望这有助于！ - Agor

Hope this helps! - Agor

编辑：希望链接现在正常工作。如果不是，它只是谷歌。 ：）

I hope the link works now. If not, just google it. :)

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