Dijkstra、Floyd算法Matlab,Lingo实现.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

第1页 / 共4页

iamzhongjiming-5324707-Dijkstra、Floyd算法Matlab,Lingo实现.doc.pdf-第2页.png

第2页 / 共4页

iamzhongjiming-5324707-Dijkstra、Floyd算法Matlab,Lingo实现.doc.pdf-第3页.png

第3页 / 共4页

iamzhongjiming-5324707-Dijkstra、Floyd算法Matlab,Lingo实现.doc.pdf-第4页.png

第4页 / 共4页

无向图的最短路问题 Lingo

Dijkstra 算法 Matlab 实现。 %求一个点到其他各点的最短路径 function [min,path]=dijkstra(w,start,terminal) %W是邻接矩阵 %start是起始点 %terminal是终止点 %min是最短路径长度 %path是最短路径 n=size(w,1); label(start)=0; f(start)=start; for i=1:n 应用举例： 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 if i~=start weight(i,i)=0; end for i=1:size(edge,2) weight(edge(1,i),edge(2,i))=edge(3,i); end [dis,path]=dijkstra(weight,1,11) label(i)=inf; end end s(1)=start; u=start; while length(s)(label(u)+w(u,v)) label(v)=(label(u)+w(u,v)); f(v)=u;

if ins==0 v=i; if k>label(v) k=label(v); v1=v; end end end s(length(s)+1)=v1; u=v1; end min=label(terminal); path(1)=terminal; i=1; while path(i)~=start path(i+1)=f(path(i)); i=i+1 ; end path(i)=start; L=length(path); path=path(L:-1:1); Floyd 算法：matlab 程序： %floyd算法， function [D,path,min1,path1]=floyd(a,start,terminal) %a是邻接矩阵 %start是起始点 %terminal是终止点 %D是最小权值表 %path是最短路线表。 D=a;n=size(D,1); path=zeros(n,n); for i=1:n 应用举例： 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]; if D(i,j)~=inf path(i,j)=j; for j=1:n [D, path]=floyd(a) end end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end end end if nargin==3 min1=D(start,terminal); m(1)=start; i=1; path1=[ ]; while k=i+1; m(k)=path(m(i),terminal); i=i+1; path(m(i),terminal)~=terminal end m(i+1)=terminal; path1=m; end Floyd 算法：Lingo 程序： !用LINGO11.0编写的FLOYD算法如下; model: sets: nodes/c1..c6/; link(nodes,nodes):w,path; !path标志最短路径上走过的顶点; path=0; w=0; @text(mydata1.txt)=@writefor(nodes(i):@writefor(nodes(j): @format(w(i,j),' 10.0f')),@newline(1)); @text(mydata1.txt)=@write(@newline(1)); @text(mydata1.txt)=@writefor(nodes(i):@writefor(nodes(j): @format(path(i,j),' 10.0f')),@newline(1)); endsets data: enddata calc: w(1,2)=50;w(1,4)=40;w(1,5)=25;w(1,6)=10; w(2,3)=15;w(2,4)=20;w(2,6)=25; w(3,4)=10;w(3,5)=20; w(4,5)=10;w(4,6)=25;w(5,6)=55; @for(link(i,j):w(i,j)=w(i,j)+w(j,i));

@for(link(i,j) |i#ne#j:w(i,j)=@if(w(i,j)#eq#0,10000,w(i,j))); @for(nodes(k): @for(nodes(i): @for(nodes(j): tm=@smin(w(i,j),w(i,k)+w(k,j)); path(i,j)=@if(w(i,j)#gt# tm,k,path(i,j));w(i,j)=tm))); endcalc end 无向图的最短路问题 Lingo model: sets: cities/1..11/; roads(cities,cities):w,x; endsets data: w=0; enddata calc: w(1,2)=2;w(1,3)=8;w(1,4)=1; w(2,3)=6;w(2,5)=1; w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2; w(4,7)=9; w(5,6)=3;w(5,8)=2;w(5,9)=9; w(6,7)=4;w(6,9)=6; w(7,9)=3;w(7,10)=1; w(8,9)=7;w(8,11)=9; w(9,10)=1;w(9,11)=2;w(10,11)=4; @for(roads(i,j):w(i,j)=w(i,j)+w(j,i)); @for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j))); endcalc n=@size(cities); !城市的个数; min=@sum(roads:w*x); @for(cities(i)|i #ne#1 #and# i #ne#n: @sum(cities(j):x(i,j))=@sum(cities(j):x(j,i))); @sum(cities(j):x(1,j))=1; @sum(cities(j):x(j,1))=0; !不能回到顶点1; @sum(cities(j):x(j,n))=1; @for(roads:@bin(x)); end

分享到：

赞收藏

资料库

Dijkstra、Floyd算法Matlab,Lingo实现.doc

相关推荐

课程资源

热门标签

最新资料