Floyd算法
给出一个图，求最短路径问题的一个O(n^3)算法
优点：容易理解，可以算出任意两个节点之间最短距离的算法，程序容易写
缺点：复杂度达到三次方，不适合计算大量数据
Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.
它的功能看上去挺强大的,但它的实现却很简单,和Washall算法很相似,也是一个三层循环,思路也是相似是,就是利用前面计算的结果:
核心思想：设立[i,j]为权值
for(k=0;k<len;k++)
for(i=0;i<len;i++)
for(j=0;j<len;j++)
if(a[k,j]+a[j,i]<a[k][i])a[k][i]=a[k,j]+a[j,i];
【用PASCAL描述】
设数组A是保存图结构的邻接矩阵,数组P是与数组A结构相同的一个数组,用于保存路径.
Floyd算法非常简单,主体就是一个三重循环,时间复杂度为O(n^3) :
For k:=1 To n Do
For i:=1 To n Do
For j:=1 To n Do
If A[i,k] + A[k,j] < A[i,j] Then
Begin
A[i,j]:=A[i,k]+A[k,j];
P[i,j]:=k;
End;
Floyd算法执行完后,数组A中保存的就是各点之间的最短路径长度.
如A[1,3],就是从1到3的最短路径的长度.
如果要求具体的路径,则要用递归和数组P:
Procedure path (i,j : Integer);
Var
k : Integer;
Begin
k := P[i,j];
If k<>0 Then
Begin
path(i,k);
Writeln(K);
path(k,j)
End;
End;
