Question

Floyd算法与Dijkstra算法的区别？

Answer 1

1、如果依次对某个顶点运用Dijkstra算法，则与Floyd算法相比，很多路径和结果计算是重复的，虽然复杂度相同，但是运算量差了很多；

2、更为重要的是：Dijkstra算法使用的前提是图中路径长度必须大于等于0；

但是Floyd算法则仅仅要求没有总和小于0的环路就可以了，因此Floyd 算法应用范围比Dijkstra算法要广。

Answer 2

我来告诉你标准答案!Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。
算法过程：1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
　
算法步骤如下：
　　1.初使时令S={V0},T={其余顶点}，T中顶点对应的距离值
　　若存在，d(V0,Vi)为弧上的权值
　　若不存在，d(V0,Vi)为∝
　　2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S
　　3.对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
　　距离值比不加W的路径要短，则修改此距离值
　　重复上述步骤2、3，直到S中包含所有顶点，即S=T为止