找到（稀疏）图的直径的好算法？
我有一个大的，连接的，稀疏图形的邻接列表形式。 我想找到两个尽可能相距很远的顶点，即图的直径和实现它的两个顶点。
我对这个问题感兴趣，无论是针对不同的应用，还是无向和有针对性的情况。 在导向的情况下，我当然关心指向距离（从一个顶点到另一个顶点的最短直接路径）。
有没有比计算所有对最短路径更好的方法？
编辑：通过“尽可能远”，我当然意味着“最长的最短路径” - 即从一个到另一个的最短距离的所有顶点对上的最大值。
那么，我已经对这个问题进行了一些思考，并且提出了一些Google搜索，我很抱歉，但是我找不到任何似乎不是“只找到所有最短路径对”的算法。
然而，如果你认为Floyd-Warshall是计算这种事情的唯一算法（Big-Theta of | V | ^ 3），那么我对你有一些好消息：Johnson的稀疏图算法（谢谢，可靠的CLRS！）计算所有对（Big-Oh（| V | ^ 2 * lgV + VE））中的最短路径，对于稀疏图应该渐近地更快。
维基百科说它适用于定向（不确定无向，但至少我想不出为什么不这样做），这里是链接。
还有关于该图的其他内容可能有用吗？ 如果它可以很容易地映射到二维平面上（因此，它的平面和边权重服从三角不等式[它可能需要满足更严格的要求，我不确定]），您可能能够分解出几何几何算法（凸包可以在nlogn中运行，并且从那里找到最远的一对点很容易）。
希望这可以帮助！ - Agor
编辑：我希望现在的链接工作。 如果没有，只需谷歌它。 :)
我不知道计算直径的更好方法，而不是所有最短路径，但Mathematica对PseudoDiameter使用以下近似值：
http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html
编辑我再次取消删除，只是让我可以继续评论。 在这个答案下，我对Johnson的算法有一些评论。 - 亚伦
我原来的评论：我也很好奇这个问题，但没有答案。 它似乎与最小生成树有关，即连接所有顶点但具有最少（或最低权重）边的子图。 这是很多算法的老问题; 其中一些似乎很容易实现。
我最初希望一旦MST被发现后直径会很明显，但我现在失去了希望:-(也许MST可以用来在直径上设置一个合理的上限，你可以用它来加速你寻找实际的直径？
链接地址: http://www.djcxy.com/p/63495.html上一篇: Good algorithm for finding the diameter of a (sparse) graph?