Question

Dijkstra算法与Floyd算法的比较问题

Dijkstra算法的复杂度为，Floyd算法的复杂度为，如果采用Dijkstra算法来计算图中任两点之间的最短距离，复杂度为，与Floyd算法相同，是否说明此时没有必要采用Floyd算法？

Answer 1

有必要，因为
1、如果依次对某个顶点运用Dijkstra算法，则与Floyd算法相比，很多路径和结果计算是重复的，虽然复杂度相同，但是运算量差了很多；
2、更为重要的是：Dijkstra算法使用的前提是图中路径长度必须大于等于0；
但是Floyd算法则仅仅要求没有总和小于0的环路就可以了
因此Floyd 算法应用范围比Dijkstra算法要广。