嘿，我正在寻找一种算法来查找无向无权图 G=(V,E) 中的直径(最长的最短路径)。
我发现的最佳解决方案是运行 BFS |V|次，运行时间:O(|V|*(|v|+|E|))。 有人能想到更有效的解决方案吗？ 即使它只是更有效率一点，我也想听听你的想法!
非常感谢:)
最佳答案
Crescenzi et al. on “On Computing the Diameter of Real-world Undirected Graphs.” (2013) 最近的一些工作提出了一种在最坏情况下运行 O(V*E) 的算法，但在许多实际应用中运行的算法是 O(V)(我认为这意味着稀疏图) )。
关于algorithm - 如何找到图形的直径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18733039/