找到(稀疏)图的直径的好算法？

Question

我有一个邻接列表形式的大型连接稀疏图.我想找到两个尽可能远的顶点,即图的直径和实现它的两个顶点.

对于不同的应用,我对无向和定向情况下的这个问题感兴趣.在定向情况下,我当然关心定向距离(从一个顶点到另一个顶点的最短有向路径).

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

编辑:通过"尽可能远的距离",我当然意味着"最长的最短路径" - 也就是说,从一个到另一个的最短距离的所有顶点对的最大值.

Answer 1

好吧,我已经对问题进行了一些思考,并且有点谷歌搜索,我很抱歉,但我找不到任何似乎不是"只找到所有对最短路径"的算法.

但是,如果你假设Floyd-Warshall是计算这类事物的唯一算法(Big-Theta of | V | ^ 3),那么我有一些好消息:Johnson的稀疏图算法(谢谢你,可靠的CLRS!)计算(Big-Oh(| V | ^ 2*lgV + VE))中的所有对最短路径,对于稀疏图,它应该渐近更快.

维基百科说它适用于定向(不确定无向,但至少我不能想到为什么不这样做),这里是链接.

图表还有什么可能有用吗？如果它可以很容易地映射到2D平面上(因此,它的平面和边缘权重服从三角形不等式[它可能需要满足更严格的要求,我不确定])你可能能够打破一些几何算法(凸壳可以在nlogn中运行,从那里可以轻松找到最远的一对点).

希望这可以帮助! - Agor

编辑:我希望链接现在有效.如果没有,只需谷歌吧.:)

Answer 2

我不知道除了所有最短路径之外的更好的计算直径的方法,但Mathematica对PseudoDiameter使用以下近似:

• 图测地线是图的两个顶点之间的最短路径.图形直径是图形的所有图形测地线的最长可能长度.伪直径找到近似图形直径.它的工作原理是从顶点u开始,找到距离u最远的顶点v.通过将v视为新的起始顶点来重复该过程,并且当图形距离不再增加时结束.选择具有最小度数的最后一个级别集合的顶点作为最终起始顶点u,并且进行遍历以查看是否可以增加图形距离.该图形距离被认为是伪直径.

http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html

Answer 3

编辑我再次取消删除，只是为了继续发表评论。我在这个答案下面对约翰逊算法有一些评论。- 亚伦

我的原始评论：我也很好奇这个问题，但没有答案。它似乎与最小生成树有关，连接所有顶点但具有最少（或最低权重）边的子图。这是许多算法的老问题；其中一些似乎很容易实现。

我最初希望一旦找到 MST，直径就会很明显，但现在我失去了希望:-( 也许 MST 可以用来给直径设置一个合理的上限，你可以用它来加速您搜索的是实际直径吗？