《最短路径算法之总结》由会员分享，可在线阅读，更多相关《最短路径算法之总结（6页珍藏版）》请在金锄头文库上搜索。
1、：求解最短路径的 Dijkstra 算法(1)给起点Vs赋以标号k，s),并将起点Vs放在集合S中，其它点放在集合T中。2)对图G里起点在集合S中，终点在集合T中的边e.或弧a，计算9 = minminp2Minp=minp2;毁掉前记录，从新记录顶点 jN 与 iNN；EndIf Minp=minp2Minp=minp2;记录顶点 jN 与 iNN；EndEndEnd%上 For 循环结束，表找最短路 向前推进一次。%记录上面寻找的最短路。修改By (jN, iNN)=1； 表示iNN为到jN前一个顶点修改 Vs( jN，：)；End子函数：找出顶点iN到外的最短路长与顶点号minp2,jN
2、；Function jN, Minp2 =Minp(AyI, Vs )Minp2=Inf ;For tN=1:length(AyI)If Minp2 AyI( tN )&Vs(tN,1)=0Minp2=AyI(tN); jN=tN;EndEnd四：代码function f=MinPath() %记所求起点为0,终点NNNN,Ay=l ni tGraph();By=zeros(NN);Vs=zeros(NN,2);Vs(1,1)=1; %起点放入集合VsJiLuQia n=zeros(1,NN); is=1; %记录前一顶点while Vs(NN,1)=1 %结束顶点Min p=i nf; jN
3、0=0;for iN=1:NNif Vs(iN,1)=1Mi np2,jN=Mi npa(Ay(iN,:),Vs);Min p2=Mi np2+Vs(iN,2);%寻之后，jN 一个；而它前一个顶点可能有多个if MinpMinp2Mi np=Mi np2; jNO=jN;is=1; JiLuQian( 1,is)=iN; continue ;endif Minp =Minp2&jN0=jN;%排除同时多条路径相等，但到达顶点不相同is=is+1; JiLuQian(1,is)=iN;endendendif Min p=i nfdisp(不能找到通路到所求顶点！)；break;endVs(jN
4、0,:)=1,Mi np;isl=1;while islv=isBy(jN0,JiLuQia n(1,isl)=1 ;isl=isl+1;endend%回搜By找最短路径输出Search( By, NN, NN);f=Vs(NN,2);end%顶点到外的最小路经fun ctio n Mi np2,jN=Mi npa(Ayl,Vs)Min p2=i nf;jN=;for tN=1:le ngth(Ayl)if Mi np2 AyI(tN) & Vs(tN,1)=0 %找一顶点到外的最小路经Min p2=Ayl(tN);jN=tN;endendend%回寻输出最短路径function tp=Sea
5、rch( By, NN,jv)tp=1;if jv=1retur n;endit=1；while itvNNif By(jv,it)=OSearch( By, NN, it); fpri ntf(1,%d-,it);if jv=NNfpr in tf(1,%dn,NN);endendit=it+1;endend%建立图形fun ctio n NN,Ay=l ni tGraph()%顶点列:12345%顶点行Ay= Inf 12Inf Inf% 1InfInfInf35%2Inf43InfInf%3InfInfInfInf2%4Inf Inf Inf Inf Inf % 5NN= 5 ; %表示领接矩阵的行列数，即图的顶点数% 建立图的领接链表%NN= input(请输入顶点数：)；%Ay=zeros(NN); Ay(:,:)=i nf;%disp(输入弧的起点，终点，权值(输入都为0结束)！);%v0=i nput(v0= );v1=i nput(v1= );dis=i nput(dis=);%while v0=0|v1=0|dis=0% Ay(v0,v1)=dis;% v0=input(v0= );v1=input(v1= );dis=input(dis=);%e nd% 建立图的领接链表end
