%floyd算法計算最短路徑，輸入a為賦權鄰接矩陣
function [D,path]=floyd(a)
a={0,3,7,0,0,0
         3,0,2,5,4,0
         7,2,0,1,4,0
         0,5,1,0,2,8
         0,4,4,2,0,3
         0,0,0,8,3,0};
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
    for j=1:n
        if D(i,j)~=inf
            path(i,j)=j;
        end
    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);
                path(i,j)=path(i,k)
            end
        end
    end
end