暴強(qiáng)Dijkstra算法求任意兩點(diǎn)間最短路徑(matlab程序)

暴強(qiáng)Dijkstra算法求任意兩點(diǎn)間最短路徑(matlab程序)暴強(qiáng)Dijkstra算法求任意兩點(diǎn)間最短路徑(matlab程序)暴強(qiáng)Dijkstra算法求任意兩點(diǎn)間最短路徑(matlab程序)資料僅供參考文件編號(hào)：2022年4月暴強(qiáng)Dijkstra算法求任意兩點(diǎn)間最短路徑(matlab程序)版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：效果展示：開(kāi)頭輸入的是點(diǎn)的序列號(hào)（表示第幾個(gè)點(diǎn)），顯示的是最短路徑的走法（同樣以點(diǎn)的序列號(hào)顯示，表示途徑的第幾個(gè)點(diǎn)）。%編寫(xiě)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&&t>0p=parent(t);path=[ppath(1:count)];t=p;count=count+1;endifcount>=2*nerror(['Thepathpreallocationlengthistooshort.',...'Pleaseredefinepathpreallocationparameter.']);endpath(1)=s;path=path(1:count);%算法實(shí)現(xiàn)clc;clear;closeall;%%載入設(shè)置數(shù)據(jù)lines=load('');%點(diǎn)與點(diǎn)之間的距離矩陣A=lines;A(find(A>10))=inf;%對(duì)步長(zhǎng)的限制，根據(jù)自己的要求決定！我們?cè)诖诉x擇10.%A就是連接矩陣，其中對(duì)角線為0，表示本身%有連接關(guān)系的就對(duì)應(yīng)線的長(zhǎng)度%沒(méi)有連接關(guān)系的就對(duì)應(yīng)inf%%下面的是dijstra算法，有兩種方式可以調(diào)用s=input('輸入起點(diǎn)');%起點(diǎn)（點(diǎn)的序號(hào)）e=input('輸入終點(diǎn)');%終點(diǎn)（點(diǎn)的序號(hào)）[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(pat