暴强Dijkstra算法求任意两点间最短路径(matlab程序)

效果展示：开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。%编写m文件function[distance,path]=dijkstra(A,s,e)%[DISTANCE,PATH]=DIJKSTRA(A,S,E)%returnsthedistanceandpathbetweenthestartnodeandtheendnode.%%A:adjcentmatrix%s:startnode%e:endnode%initializen=size(A,1);%nodenumberD=A(s,:);%distancevectorpath=[];%pathvectorvisit=ones(1,n);%nodevisibilityvisit(s)=0;%sourcenodeisunvisibleparent=zeros(1,n);%parentnode%theshortestdistancefori=1:n-1%BlueSethasn-1nodestemp=zeros(1,n);count=0;forj=1:nifvisit(j)temp=[temp(1:count)D(j)];elsetemp=[temp(1:count)inf];endcount=count+1;end[value,index]=min(temp);j=index;visit(j)=0;fork=1:nifD(k)D(j)+A(j,k)D(k)=D(j)+A(j,k);parent(k)=j;endendenddistance=D(e);%theshortestdistancepathifparent(e)==0return;endpath=zeros(1,2*n);%pathpreallocationt=e;path(1)=t;count=1;whilet~=s&&t0p=parent(t);path=[ppath(1:count)];t=p;count=count+1;endifcount=2*nerror(['Thepathpreallocationlengthistooshort.',...'Pleaseredefinepathpreallocationparameter.']);endpath(1)=s;path=path(1:count);%算法实现clc;clear;closeall;%%载入设置数据lines=load('Distance.txt');%点与点之间的距离矩阵A=lines;A(find(A10))=inf;%对步长的限制，根据自己的要求决定！我们在此选择10.%A就是连接矩阵，其中对角线为0，表示本身%有连接关系的就对应线的长度%没有连接关系的就对应inf%%下面的是dijstra算法，有两种方式可以调用s=input('输入起点');%起点（点的序号）e=input('输入终点');%终点（点的序号）[distance,path0]=dijkstra(A,s,e);fprintf('\nUseDijkstratheMinDistanceis:%.5f\n',distance);fprintf('\nUseDijkstratheMinDistancepathis:\n');disp(path0);A1=A;A1(isinf(A1))=0;[d,p,pred]=graphshortestpath(sparse(A1),s,e);fprintf('\nUsegraphshortestpaththeMinDistanceis:%.5f\n',d);fprintf('\nUsegraphshortestpaththeMinDistancepathis:\n');disp(p);fori=1:length(path0)ifi==length(path0)temp=[path0(1)path0(i)];elsetemp=[path0(i)path0(i+1)];endend