path_1.m

使用FLORD算法求解任意两顶点间最短路的MATLAB程序示例代码

clear;clc;
%依次输入起始点和终点
sp=input('start point:');ep=input('end point:');              
%邻接矩阵
a =[0,50,999999,40,25,999999,30,999999,50,999999;50,0,30,999999,35,50,999999,60,999999,999999;999999,30,0,15,999999,30,50,25,999999,60;40,999999,15,0,45,30,55,20,40,65;25,15,999999,45,0,60,10,30,999999,55;999999,50,30,30,60,0,25,55,35,999999;30,999999,50,999999,10,25,0,30,45,60;999999,60,25,20,30,55,30,0,10,999999;20,999999,999999,40,999999,15,25,45,0,20;35,20,10,45,20,999999,60,999999,30,0;];
path=zeros(length(a));
b=a;
%Ford算法
for k=1:10
    for i=1:10
        for j=1:10
            if b(i,j)>b(i,k)+b(k,j)
                b(i,j)=b(i,k)+b(k,j);
                path(i,j)=k;
            end
        end
    end
end
min=b(sp,ep);
%路径的直观表达
path_f=ep;
while path(sp,ep)~=0
    path_f=[path_f,path(sp,ep)];
    ep=path(sp,ep);
end
path_f=[path_f,sp];path_f=fliplr(path_f);
path_f
min