嘿，我正在寻找一种算法来在无向无权图 G =（V，E）中找到直径（最长的最短路径）。
我找到的最佳解决方案是运行 BFS |V| 次，运行时间：O(|V|*(|v|+|E|))。有人能想到更有效的解决方案吗？即使它只是更有效一点我想听听你的想法！
多谢 ：）
问问题
3071 次
1 回答
4
Crescenzi 等人最近做了一些工作。关于“计算真实世界无向图的直径”。（2013）提出了一种在O(V*E)最坏情况下运行的算法，但O(V)在许多实际应用中（我认为这意味着稀疏图）。
于 2013-09-11T14:49:24.560 回答