弗洛伊德算法(弗洛伊德算法求出最短距离)-稻草人资讯

Floyd算法与Dijkstra算法的区别？

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

Floyd算法与Dijkstra算法的不同

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为止。

Floyd算法思想

算法描述：(1) 用数组dis[i][j]来记录i,j之间的最短距离。

初始化dis[i][j],若i=j则dis[i][j]=0,若i,j之间有边连接则dis[i][j]的值为该边的权值，否则dis[i][j]的值为。

(2) 对所有的k值从1到n，修正任意两点之间的最短距离，计算dis[i][k]+dis[k][j]的值，若小于dis[i][j],则dis[i][j]= dis[i][k]+dis[k][j]，否则dis[i][j]的值不变。

程序：void Floyd(int dis[n+1][n+1],int path[n+1][n+1],int n){ int i,j,k;
for(k=1;
k<
=n;
k++) for(i=1;
i<
=n;
i++) for(j=1;
j<
=n;
j++) if(dis[i][k]+dis[k][j]<
dis[i][j]){ dis[i][j] = dis[i][k]+dis[k][j];
Path[i][j]=k;
}}正确性证明(归纳法) ：对于任意两点A，B：（1）当从A到B之间的最短路径，在中间没有经过顶点或经过1个顶点号为1的顶点时，算法显然正确。

（2）假设A到B经过的最大顶点号不超过k-1时，算法得到的最短距离是正确的（3）当A到B经过的最大顶点号为k时，则从A到顶点号为k的顶点v 之间的顶点号均不大于k-1，从v 到B之间的顶点号也不大于k-1，由假设2得，A到vk的距离是中间顶点号不超过k-1的最短距离，vk到B的距离是中间顶点号不超过k-1的最短距离，所以A经vk到B为A，B之间经过最大号为k的路径中距离最短的，由算法修正A，B的最短距离，即可得到A，B间顶点号不超过k的最短距离。

（4）综上所述，算法是正确的时间复杂度：O（n3）。