文档介绍：Floyd算法
算法能实现求一个图中任意两点间最断距离,并给出路径。
设图G的顶点数为n,D=(dij)n×n,为其距离矩阵,Floyd算法步骤如下:
Step 1:输入距离矩阵D;
Step 2:k=1,
Step 3:i=1;
Step 4:dij=min(dij,dik+dkj),j=1,2,…,n;
Step 5:i++;如果i≤n,转Step 4;
Step 6:k++;如果k≤n,转Step 3;否则转Step 7;
Step 7:程序结束,输出结果。
用Floyd算法求图中各顶点之间的最短路的Matlab程序。
M=99999;
a=[0,20,14,M,M,M,M
M,0,M,15,12,M,M
M,M,0,10,M,13,M
M,M,M,0,8,M,9
M,M,M,M,0,8,10
M,M,M,M,M,0,12
M,M,M,M,M,M,0];
length=floyd(a)
r代表任意城市之间经过的路径,这个结果比起Mathematica来说不好理解,这个也是我自己对比上面结果的理解。
第一行代表1经过1,2,3,4,5,6,7的路径;
第一个数是1,代表1直接到1最短(1,1)
第二个数是2,代表1直接到2最短(1,2)
第三个数是3,代表1直接到3最短(1,3)
第四个数是3,代表1经过3再到4最短(1,3,4)
第五个数是2,代表1经过2再到5最短(1,2,5)
第六个数是3,代表1经过3再到6最短(1,3,6)
第七个数是3,代表1经过3再到7最短(1,3,7)??和前面不一样
出现问题了,其实错误在于3不是直接到7最短造成的(我们取的3到7距离为99999) 而前面3个红色的路径是不会出现这种情况的(可以看下面的表)。
可以看第三行
3是经过4再到7最短! 所以(1,3,4,7)
任意城市之间经过的路径我们只需要求红色括号