求任意两点之间的最短距离的Floyd算法及其MATLAB实现

算法思想

如果中转点为K
当D(i,K)+D(K,j)<D(i,j)
则D(i,j)=D(i,K)+D(K,j)
否则不变

程序的参数说明

P为最短路，顶点以经过次序排序
u为最短距离
W为距离矩阵
k1为起始点
k2为终止点

MATLAB实现

function [P, u] = Floyd(W,k1,k2)
n = length(W);
m = 1;
U = W;
while m <= n
    for i = 1 : n
        for j = 1 : n
            if U(i,j) > U(i,m) + U(m,j);
                U(i,j) = U(i,m) + U(m,j);
            end
        end
    end
    m = m + 1;
end
u = U(k1,k2);

P1 = zeros(1,n);
k = 1;
P1(k) = k2;
V = ones(1,n)*inf;
kk = k2;
while kk ~= k1
    for i = 1 : n
        V(1,i) = U(k1,kk) - W(i,kk);
        if V(1,i) == U(k1,i)
            P1(k+1) = i;
            kk = i;
            k = k + 1;
        end
    end
end
k = 1;
wrow = find(P1 ~= 0);
for j = length(wrow) : (-1) : 1
    P(k) = P1(wrow(j));
    k = k + 1;
end
P;

测试

测试用例：A=

	[0  2  6  4;
    inf 0 3 inf;
    7 inf 0  1 ;
    5 inf 12 0];

测试结果
P =

 1     2     3

u =

 5