计算所有点对最短路径，神马算法最高效？

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

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