最长路算法 和 最短路算法 matlab.doc

《最长路算法 和 最短路算法 matlab.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*最长路function[l,t]=dijkstra_long(A,v)n=length(A);V=1:n;s=v;l=A(v,:);t=v.*ones(1,n);ss=setdiff(V,s);nn=length(ss);forj=1:n-1k=ss(1);fori=1:nnifl(k)

2、iflength(s)==nbreak;elsefori=1:nnifl(ss(i))==infl(ss(i))=0;endform=1:nnifl(ss(i))

3、dendend最短路function[l,t]=dijkstra1(A,v)%dijkstra最短路算法,某个顶点v到其余顶点的最短路%例：A=[0281infinfinfinf%206inf1infinfinf%8607512inf%1inf70infinf9inf%inf15inf03inf8%infinf1inf3046%infinf29inf403%infinfinfinf8630];n=length(A);%顶点个数V=1:n;%顶点集合s=v;%已经找到最短路的点集，初始为vl=A(v,:);%当前v点到各个点

4、的距离，初始为直接距离t=v.*ones(1,n);%当前距离时点的父顶点，初始都为vss=setdiff(V,s);nn=length(ss);%还没有找到最短路的点集forj=1:n-1%一共进行n-1次迭代k=ss(1);fori=1:nn%对还没有找到最短路的点ifl(k)>l(ss(i))k=ss(i);l(k)=l(ss(i));%在当前一行距离中取最小值endendifl(k)==inf%如果当前行最小值是无穷大，则结束break;else%否则k点的最短路找到s=union(s,k);ss=setdiff(

5、V,s);nn=length(ss);endiflength(s)==n%全部点的最短路都找到break;elsefori=1:nn%以k为生长点，如果通过k点会更短，则更改当前最短距离ifl(ss(i))>l(k)+A(k,ss(i))l(ss(i))=l(k)+A(k,ss(i));t(ss(i))=k;endendendend