|
floyd （弗洛伊德算法）Dijkstra（迪杰斯特拉算法）bellman-ford（贝尔曼夫德算法）spfa空间复杂度 O（N²）O（M） O（M）O（M）时间复杂度O（N³）O（（m+n）logN）O（MN）最坏也是O（NM）适用情况稠密图和顶点关系密切稠密图和顶点关系密切稀疏图和边关系密切稀疏图和边关系密切负权可以不能可以可以有负权边时可否处理可以不能可以可以判断是否存在负权回路不能不能可以可以
其中N表示点数，M表示边数
Floyd 算法虽然总体上时间复杂度较高，但可以处理带负权边的图（但不能有负权回路），并且均摊到每一点对上，在所有的算法中还是属于比较优秀的算法。另外，floyd算法较小的编码复杂度也是一大优势，所以，如果要求的是所有点对间的最短路径，或者如果数据范围较小，则floyd算法比较合适。
Dijkstra算法最大的弊端就是他无法处理带有负权边以及负权回路的图，但是Dijkstra算法具有良好的可扩展性，扩展后可以适应很多问题。另外用堆优化的Dijkstra算法的时间复杂度可以达到O（M log N）。当边有负权，甚至存在负权回路时，需要使用Bellman-ford 算法或者队列优化的Bellman-ford算法，因此我们选择最短路径法时，根据实际的需求和每一种算法的特性，选择合适的算法来使用。
|