find（稀疏）图的直径的好algorithm？
我有一个大的，连接，稀疏graphics的邻接表格forms。 我想find两个尽可能相距较远的顶点，即图的直径和实现它的两个顶点。
我对这个问题感兴趣，无论是针对不同的应用程序，还是无向和有针对性的案例。 在有针对性的情况下，我当然关心指向距离（从一个顶点到另一个顶点的最短的有向path）。
有没有比计算所有对最短path更好的方法？
编辑 ：通过“尽可能远”，我当然是指“最长的最短path” – 即从一个到另一个的最短距离的所有顶点对的最大值。
那么，我已经对这个问题进行了一些思考，还有一些Googlesearch，对不起，但我找不到任何似乎不是“只find所有对最短path”的algorithm， 。
但是，如果你认为Floyd-Warshall是计算这种事情的唯一algorithm（Big-Theta of | V | ^ 3），那么我对你有一些好消息：Johnson的稀疏图algorithm（谢谢，可靠的CLRS！）计算所有对（Big-Oh（| V | ^ 2 * lgV + VE））中的最短path，对于稀疏图应该渐近地更快。
维基百科说，它适用于指导（不知道关于无向，但至less我不能想到一个原因为什么不），这里的链接 。
还有关于图表的其他内容可能有用吗？ 如果它可以很容易地映射到二维平面上（所以它的平面和边权重服从三angular不等式[它可能需要满足更严格的要求，我不确定]），你可能能够打破一些几何algorithm（凸包可以在nlogn中运行，从那里find最远的一对点很容易）。
希望这可以帮助！ – Agor
编辑：我希望现在的链接工作。 如果没有，只是谷歌它。 🙂
我不知道计算直径的方法不是所有最短path，但Mathematica对PseudoDiameter使用以下近似值：
- 图测地线是图的两个顶点之间的最短path。 图直径是图的所有图测地线的最长可能长度。 PseudoDiameterfind一个近似的graphics直径。 它从一个顶点u开始，find一个离你最远的顶点v。 通过将v作为新的起始顶点来重复该过程，并在图距离不再增加时结束。 select具有最小程度的最后一个等级集合的顶点作为最终的起始顶点u，并且遍历完成以查看graphics距离是否可以增加。 这个图表距离被认为是伪直径。
http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html
这里有一些关于在无向图中比所有对最短path做得更好的想法，虽然我不确定它会有多大的改进。
这里有一个子程序，如果有的话，将find距离D的两个节点。 select一个任意节点x并计算M [x] =从x到任何其他节点的最大距离（使用任何单个源最短pathalgorithm）。 如果M [x]> = D，那么x是我们的节点之一，另一个很容易find。 然而，如果M [x] <D，那么我们要找的两个端点都可能小于距离x的距离D – M [x]（因为从该节点到所有其他节点的path到x的距离< d）。 所以find距离x的距离小于DM [x]的所有节点并标记为不良。 select一个新的x，这次确保我们避免所有标记为坏的节点，然后重复。 希望我们将很多节点标记为坏，所以我们必须比| V |less得多 最短path计算。
现在我们只需要设置D = diam（G）并运行上面的程序。 我们不知道直径（G）是多less，但是对于任何x，M [x] <= diam（G）<= 2M [x]我们可以得到一个相当窄的范围。 select几个x开始，为每个计算M [x]，然后计算直径（G）的上下限。 然后，我们可以在结果范围内进行二分search，使用上述过程find猜测长度的path（如果有的话）。
当然，这只是无向的。 我想你可以用有向图做一个类似的scheme。 坏节点是那些可以达到小于DM [x]的x，并且diam（G）的上界不起作用，所以您需要更大的二进制search范围。
编辑我再次取消删除，只是让我可以继续评论。 在这个答案下，我对Johnson的algorithm有一些评论。 – 亚伦
我原来的评论 ：我也很好奇这个问题，但没有答案。 它似乎与最小生成树有关，即连接所有顶点但具有最less（或最低权重）边的子图。 这是很多algorithm的老问题; 其中一些似乎很容易实施。
我最初希望一旦MST被发现，直径就会很明显，但现在我失去了希望:-(也许MST可以用来在直径上设置一个合理的上限，可以用来加速你的实际直径的search？
不知道它是否符合法案，但有趣的是：
HADI：使用Hadoop的大规模图的快速直径估计和挖掘
U.Cang，C.Sourakakis，APAppel，C.Faloutsos，J.Leskovec，“HADI：FastDimemeter Estimation and Mining in Massive Graphs with Hadoop”，CMU ML Tech Report CMU-ML-08-117,2008。
如果graphics是一棵树（和无向）。 你可以简单地运行2个dfs的。 从随机节点u和dfs开始，find最远的节点v，然后从v开始，find最长的长度。 那个长度是最佳的
原谅我，如果我的答案是不正确的语法方面，但我的algorithm课程是前一段时间（而不是英文）。
如果我正确地理解了你的问题，你想知道从节点A开始到达节点B而没有“回溯”你的步骤，你可以计算出的最高数目是多less。 如果是这种情况，我会想象你的图是非循环的（循环选项来的晚）。
首先，上限是边的数量。 我如何看待这个问题是：取一个节点，创build一个树，其中的节点位于根节点，每个后续节点都可以到达下一个节点。 你build立的树的高度是直径，叶子是在那个距离的节点。 如果那个距离=你完成的边数。 如果没有，select另一个节点并重复。
我认为这与build立广度优先search相似。 如果不了解图表，可以采用一些启发式方法来查看哪个树的方向（即哪个节点应该先被选取）会更好，但这是另一个话题。
关于图的周期性 – 正如其他人指出的那样可能导致无限循环。 摆脱这些的方法可能是“排除”属于一个循环的节点，并在它们之间添加最长的path，作为通过input循环并从其中出来的值获得的值，只触摸每个节点一次。
现在，正如我所说的，这种方法可以很容易地和做全对最短path一样。 最坏情况下的复杂性肯定是相同的，否则就不可能。
我真的怀疑，有没有find最长最短path的方法，而不必使用某种所有对最短pathalgorithm（重复查找单个源最短path基本上是在最坏的情况下做所有的对）。
如果graphics不是树或DAG，那么'直径'很难用“最长path”来定义。 如果图中有周期，那么“最长”的path可以是无限的。 因此，图的简单遍历不能产生所有节点上最长的path。 既然你已经说过你的图不一定是非循环的，而且你对“最长最短”path感兴趣，似乎没有任何方法可以避免find所有节点的最短path。 正如阿戈尔所说，使用约翰逊的algorithm可能是最好的。
你当然可以采用基于启发式的方法。 使用伪周边顶点的algorithm似乎是最常用的方法。
获得这个数字估计的一个方法是从一个随机点开始，并且做一个广度优先的“草火”algorithm，标记到每个节点的最短距离。 这里最长的距离是你的估计。
用不同的起点多次运行这个非常快的algorithm，然后取得最大值将提高估计的准确性，当然，给你一个体面的下限。 根据图表的分布和连通性，这个估计甚至可能是准确的！
如果图表足够大，则在添加更多样本时渐近估计值的变化分析可能允许您进行更好的猜测。
如果你对一个确切的答案感兴趣，似乎不太可能逃避太多的angular落，除非你的graphics很容易被分割成彼此之间弱连接的组件 – 在这种情况下，你可以限制你的search到最短不同组件中所有顶点对之间的path。
select一个顶点v并执行BFS（v），这将计算从v到所有顶点的距离。 获得最长的距离。 这是O（V + E）
现在针对所有v个顶点运行此algorithm，并选取这些最长距离的最大值。 整体复杂度：O（V *（V + E））
肮脏的方法：
我们知道，对于| V | = n和| E | = m的图G（V，E），Dijkstraalgorithm运行在O(m+nlogn) ，这是一个单一的来源。 对于所有对问题，您需要为每个节点运行Dijkstra作为起点。
但是，如果你有很多机器，你可以很容易地平行这个过程。
这个方法最容易实现，绝对不是很好。
是的，有一个更好的方法来find图的直径。 在这里，我做了一个简单的课程来演示它。 顶点将是你的图上的点。
public class MyTestClass { //Simple Point struct struct Vertex { public float X, Y; public Vertex(float pX, float pY) { X = pX; Y = pY; } } //For getting the bounds of your graph struct BoundingBox { public float Left, Right, Bottom, Top; public BoundingBox(float pLeft, float pRight, float pBottom, float pTop) { Left = pLeft; Right = pRight; Bottom = pBottom; Top = pTop; } } //Properties Vertex[] vertices; BoundingBox bound; float diameter; //Constructor //Here is the fastest way to get the diameter >> public MyTestClass() { //Init objects vertices = new Vertex[100]; for(int i = 0; i != vertices.Length; ++i) vertices[i] = new Vertex(i, i); bound = new BoundingBox(vertices[0].X, vertices[0].X, vertices[0].Y, vertices[0].Y); //Calculate BoundingBox for(int i = 0; i != vertices.Length; ++i) { bound.Left = (vertices[i].X <= bound.Left) ? vertices[i].X:bound.Left; bound.Right = (vertices[i].X >= bound.Right) ? vertices[i].X:bound.Right; bound.Bottom = (vertices[i].Y <= bound.Bottom) ? vertices[i].Y:bound.Bottom;//NOTE: If Y is faces down, then flip bottom & top comparison bound.Top = (vertices[i].Y >= bound.Top) ? vertices[i].Y:bound.Top; } //Messure Size of the BoundingBox float vecX = (bound.Right-bound.Left); float vecY = (bound.Top-bound.Bottom); diameter = (float)System.Math.Sqrt((vecX*vecX) + (vecY*vecY)); } }
