已知一个图是完全图，在计算所有点对的最短路径问题中，采用什么算法比较高效
Dijkstra算法肯定不是最高效的
动态规划？ 还是采用A*算法？或者其他算法？
A*算法需要指定起始点和终点，算法完成后，得到一对节点间的最短路径。如果要计算所有点对间的最短路径，A*算法要怎么操作（难道要用枚举？）

还有就是采用动态规划的方法时，如何保存最短的路径？（算法最后应该输出点对之间的最短路径）

floyed

貌似floyed与动态规划的方法没有本质的区别？都是O(N^3)

[ 本帖最后由 ronan_ly 于 2011-3-8 17:15 编辑 ]

图啊。。。

floyed就是dp

能否用LCA算法在O（n+n^2）做呢  只是猜想