《Dijkstra、Floyd算法Matlab_Lingo实现》由会员分享，可在线阅读，更多相关《Dijkstra、Floyd算法Matlab_Lingo实现（11页珍藏版）》请在装配图网上搜索。
1、Dijkstra算法Matlab实现。%求一种点到其他各点旳最短途径function min,path=dijkstra(w,start,terminal)%W是邻接矩阵应用举例：edge=2,3,1,3,3,5,4,4,1,7,6,6,5,5,11,1,8,6,9,10,8,9, 9,10;.3,4,2,7,5,3,5,11,7,6,7,5,6,11,5,8,1,9,5,11,9,8,10,9;.3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7,2,9,9,2,2;n=11; weight=inf*ones(n,n);for i=1:n weight(i,i)
2、=0;endfor i=1:size(edge,2) weight(edge(1,i),edge(2,i)=edge(3,i);enddis,path=dijkstra(weight,1,11)%start是起始点%terminal是终结点%min是最短途径长度%path是最短途径n=size(w,1); label(start)=0; f(start)=start;for i=1:n if i=start label(i)=inf; endends(1)=start; u=start;while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u
3、,v); f(v)=u; end end end v1=0; k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end end if ins=0 v=i; if klabel(v) k=label(v); v1=v; end end end s(length(s)+1)=v1; u=v1;endmin=label(terminal); path(1)=terminal;i=1; while path(i)=start path(i+1)=f(path(i); i=i+1 ;endpath(i)=start;L=length(p
4、ath);path=path(L:-1:1);Floyd算法：matlab程序：%floyd算法，function D,path,min1,path1=floyd(a,start,terminal)%a是邻接矩阵%start是起始点%terminal是终结点应用举例：a= 0,50,inf,40,25,10 50,0,15,20,inf,25 inf,15,0,10,20,inf 40,20,10,0,10,25 25,inf,20,10,0,55 10,25,inf,25,55,0;D, path=floyd(a) %D是最小权值表%path是最短路线表。D=a;n=size(D,1);pa
5、th=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)1;for(dian(i)|i#gt#1:sum(dian(j)|j#ne#i:x(j,i)=1);for(dian(i)|i#gt#1:for(dian(j)|j#ne#i#and#j#gt#1:level(j)level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(dian(i)|i#gt#1:level(i)n-1-(n-2)*x(1,i);for(dian(i)|i#gt#1:bnd(1,level(i),100000);for(link:bin(x);
Dijkstra、Floyd算法Matlab_Lingo实现
