lujin2.m

最短路径问题（包括Floyd算法和避圈法）的matlab程序

a=[0 2 4 inf 6
   3 0 5 3 13
   5 11 0 21 inf
   10 2 5 0 11
   inf 23 1 9 0];%a为n*n的矩阵，0表示顶点到本身的距离，不相连的两个顶点的距离用inf表示
n=size(a,1);
D=a;     %赋初值
for i=1:n
    for j=1:n
        R(i,j)=j;
    end
end   %赋路径初值
for k=1:n
    for i=1:n
        for j=1:n
            if D(i,k)+D(k,j)<D(i,j)  
                D(i,j)=D(i,k)+D(k,j);%更新Dij
                R(i,j)=k;%更新Rij
            end
        end
    end
    k    %显示迭代的步数
    D    %显示每一步迭代后的路长
    R    %显示每一步迭代后的路径
    path=0;   %含有负权时
    for i=1:n
        if D(i,i)<0
            path=1;   %存在一条含有顶点Vi的负回路
            break
        end
    end
    if path
        break   
    end    %存在一条负回路，终止程序
end     %终止程序