代码来源：《图论算法及其matlab实现》（北京航空航天出版社）

P22

 

 

 

此代码返回第一个点和最后一个点之间最短路径，以及最短路径的长度。

代码如下：

 

1 function [P,u ] = Floyd(W) 2 %W表示权值矩阵 3 %P表示最短路径 4 %u表示最短路的权和 5 n=length(W); 6 U=W; 7 m=1; 8  9 while m<=n   %判断是否满足停止条件10     for i=1:n11         for j=1:n12             if U(i,j)>U(i,m)+U(m,j)13                 U(i,j)=U(i,m)+U(m,j);   %更新dij14             end15         end16     end17     m=m+1;18 end19 u=U(1,n);20 21 %输出最短路的顶点22 P1=zeros(1,n);23 k=1;24 P1(k)=n;25 V=ones(1,n)*inf;26 kk=n;27 while kk~=128     for i=1:n29         V(1,i)=U(1,kk)-W(i,kk);30         if V(1,i)==U(1,i)31             P1(k+1)=i;32             kk=i;33             k=k+1;34         end35     end36 end37 k=1;38 wrow=find(P1~=0);39 for j=length(wrow):(-1):140     P(k)=P1(wrow(j));41     k=k+1;42 end                               43 44 end

验证：

n=12;a=ones(n)+inf;for i=1:na(i,i)=0;enda(1,2)=5;a(2,3)=8;a(2,6)=5;a(3,4)=3;a(3,9)=10;a(4,5)=5;a(4,7)=3;a(5,6)=2;a(7,8)=2;a(8,9)=4;a(8,11)=6;a(9,10)=3;a(10,11)=5;a(10,12)=3;[P u ] = Floyd(a)

运行结果：

P =     1     2     3     9    10    12u =    29