6 图论matlab.doc

【任意两点间的最短路】一Dijkstra算法先建个dijkstra.m文件：function min,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;for i=1:n if i=start label(i)=inf;end, ends(1)=start; u=start;while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,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 ;end path(i)=start;L=length(path);path=path(L:-1:1);然后：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)=0;endfor i=1:size(edge,2)weight(edge(1, i), edge(2, i)=edge(3, i);enddis, path=dijkstra(weight, 1, 11) %表示1到11的距离%注意：weight是每个点到其他相邻点的距离；而edge为每个点指向的.edge=1 ; 2 ;3表示1到2经过路径距离3注：可用以下代替qi_shi=input(请输入起始位置（111）:);jie_wei=input(请输入终点位置数值（111):);dis, path=dijkstra(weight, qi_shi,jie_wei) 二Floyd算法Floyd算法函数文件function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,endif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end 主文件：e= 0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0;% 个点到其他相邻点的距离ju_li, path=floyd(e) %ju-li为任意俩点最小距离，path为到达终点的前一个节点。小例题：Warshall-Floyd 算法解：用Warshall-Floyd 算法, MATLAB 程序代码如下：n=8;A=0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0; % MATLAB 中, Inf 表示D=A; %赋初值for(i=1:n)for(j=1:n)R(i,j)=j;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,j)=D(i,k)+D(k,j); %更新dijR(i,j)=k;end;end;end %更新rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for i=1:n %含有负权时if(D(i,i)0)pd=1;break;end;end %存在一条含有顶点vi 的负回路if(pd)break;end %存在一条负回路, 终止程序end %程序结束结果k = 1D = 0 2 8 1 Inf Inf Inf Inf 2 0 6 3 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 5 6 7 8 1 2 3 1 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8k = 2D = 0 2 8 1 3 Inf Inf Inf 2 0 6 3 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 Inf 9 Inf 3 1 5 4 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 2 6 7 8 1 2 3 1 5 6 7 8 1 2 3 4 5 6 7 8 1 1 3 4 2 6 7 8 2 2 3 2 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8k = 3D = 0 2 8 1 3 9 10 Inf 2 0 6 3 1 7 8 Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 8 9 Inf 3 1 5 4 0 3 7 8 9 7 1 8 3 0 3 6 10 8 2 9 7 3 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 2 3 3 8 1 2 3 1 5 3 3 8 1 2 3 4 5 6 7 8 1 1 3 4 2 3 7 8 2 2 3 2 5 6 3 8 3 3 3 3 5 6 3 8 3 3 3 4 3 3 7 8 1 2 3 4 5 6 7 8k = 4D = 0 2 8 1 3 9 10 Inf 2 0 6 3 1 7 8 Inf 8 6 0 7 5 1 2 Inf 1 3 7 0 4 8 9 Inf 3 1 5 4 0 3 7 8 9 7 1 8 3 0 3 6 10 8 2 9 7 3 0 3 Inf Inf Inf Inf 8 6 3 0R = 1 2 3 4 2 3 3 8 1 2 3 1 5 3 3 8 1 2 3 4 5 6 7 8 1 1 3 4 2 3 7 8 2 2 3 2 5 6 3 8 3 3 3 3 5 6 3 8 3 3 3 4 3 3 7 8 1 2 3 4 5 6 7 8k = 5D = 0 2 8 1 3 6 10 11 2 0 6 3 1 4 8 9 8 6 0 7 5 1 2 13 1 3 7 0 4 7 9 12 3 1 5 4 0 3 7 8 6 4 1 7 3 0 3 6 10 8 2 9 7 3 0 3 11 9 13 12 8 6 3 0R = 1 2 3 4 2 5 3 5 1 2 3 1 5 5 3 5 1 2 3 4 5 6 7 5 1 1 3 4 2 5 7 5 2 2 3 2 5 6 3 8 5 5 3 5 5 6 3 8 3 3 3 4 3 3 7 8 5 5 5 5 5 6 7 8k = 6D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 7 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 7 12 8 6 3 0R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 6 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 6 5 5 6 7 8k = 7D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 5 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 5 12 8 6 3 0R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 7 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 7 5 5 6 7 8k = 8D = 0 2 7 1 3 6 9 11 2 0 5 3 1 4 7 9 7 5 0 7 4 1 2 5 1 3 7 0 4 7 9 12 3 1 4 4 0 3 6 8 6 4 1 7 3 0 3 6 9 7 2 9 6 3 0 3 11 9 5 12 8 6 3 0R = 1 2 6 4 2 5 6 5 1 2 6 1 5 5 6 5 6 6 3 4 6 6 7 7 1 1 3 4 2 5 7 5 2 2 6 2 5 6 6 8 5 5 3 5 5 6 3 8 6 6 3 4 6 3 7 8 5 5 7 5 5 6 7 8II网络的最大流.利用 Ford-Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：n=8;C= 0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0; %弧容量 %括号前为弧容量for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i) %选择一个已标号的点vifor(j=1:n)if(No(j)=0&f(i,j)d(i)d(j)=d(i);endelseif(No(j)=0&f(j,i)0) %对于未给标号的点vj, 当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)d(i)d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt 得到标号或者无法标号, 终止标号过程if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)if(No(t)0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)0&f(i,j)=0)a(i,j)=b(i,j);elseif(C(i,j)0&f(i,j)=C(i,j)a(j,i)=-b(i,j);elseif(C(i,j)0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;endfor(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路for(i=2:n)for(j=1:n)if(p(i)p(j)+a(j,i)p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;endif(pd)break;end;end %求最短路的Ford 算法结束if(p(n)=Inf)break;end %不存在vs 到vt 的最短路, 算法终