最大流算法
clc,clear,M=1000;
c(1,2)=3;c(1,4)=3;
c(2,3)=1;c(2,4)=20;
c(3,6)=3;
c(4,5)=10;
c(5,1)=4;c(5,3)=2;c(5,6)=13;
n=length(u);
list=[];
maxf=zeros(1:n);maxf(n)=1;
while maxf(n)>0
maxf=zeros(1,n);pred=zeros(1,n);
list=1;record=list;maxf(1)=M;
while (~isempty(list))&(maxf(n)==0)
flag=list(1);list(1)=[];
index1=(find(u(flag,:)~=0));
label1=index1(find(u(flag,index1)...
-f(flag,index1)~=0));
label1=setdiff(label1,record);
list=union(list,label1);
pred(label1(find(pred(label1)==0)))=flag;
maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1));
record=union(record,label1);
label2=find(f(:,flag)~=0);
label2=label2';
label2=setdiff(label2,record);
list=union(list,label2);
pred(label2(find(pred(label2)==0)))=-flag;
maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2);
end
if maxf(n)>0
v2=n;
v1=pred(v2);
while v2~=1
if v1>0
f(v1,v2)=f(v1,v2)+maxf(n);
else
v1=abs(v1);
f(v2,v1)=f(v2,v1)-maxf(n);
end
v2=v1;
v1=pred(v2);
end
end
end
f
function [f,wf,No]=MaxFlowMinCut_Me(n,C)
% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码
% f %显示最大流
% wf %显示最大流量
% No %显示标号, 由此可得最小割
% n 节点个数
% C %弧容量
最大流算法
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)) %选择一个已标号的点vi
for(j=1:n)if(No(j)==0&f(i,j) No(j)=i;d(j)=C(i,j)-f(i,j);pd=0; if(d(j)>d(i))d(j)=d(i);end elseif(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;end if(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(No(t),t)=f(No(t),t)-dvt;end%后向弧调整 if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end%当t 的标号为vs 时, 终止调整过程 t=No(t);end;end; %继续调整前一段弧上的流f wf=0;for(j=1:n)wf=wf+f(1,j);end end n=6; C=[0 3 0 3 0 0 0 0 1 20 0 0 0 0 0 0 0 3 0 0 0 0 10 0 0 4 2 0 0 13 0 0 0 0 0 0]; [f,wf,No]=MaxFlowMinCut_Me(n,C) 最大匹配算法 A=[1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1]; A=[1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1]; A=[1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1]; A=[1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1]; A=[1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1]; m=5;n=5;M(m,n)=0; for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end %求初始匹配M if(M(i,j))break;end;end %获得仅含一条边的初始匹配M while(1) for(i=1:m)x(i)=0;end %将记录X中点的标号和标记* for(i=1:n)y(i)=0;end %将记录Y中点的标号和标记* for(i=1:m)pd=1; %寻找X中M的所有非饱和点 for(j=1:n)if(M(i,j))pd=0;end;end if(pd)x(i)=-n-1;end;end %将X中M的所有非饱和点都给以标号0 和标记*,程序中用n+1 表示0 标号, 标号为负数时表示标记* pd=0; while(1)xi=0; for(i=1:m)if(x(i)<0)xi=i;break;end;end %假如X 中存在一个既有标号又有标记*的点, 则任取X中一个既有标号又有标记*的点xi if(xi==0)pd=1;break;end %假如X中所有有标号的点都已去掉了标记*,算法终止 x(xi)=x(xi)*(-1); %去掉xi 的标记* k=1; for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;end %对与xi 邻接且尚未给标号的yj 都给以标号i if(k>1)k=k-1; for(j=1:k)pdd=1; for(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end %将yj 在M中与之邻接的点xk (即xkyj∈M), 给以标号j 和标记* if(pdd)break;end;end if(pdd)k=1;j=yy(j); %yj 不是M的饱和点 while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j))); %任取M的一个非饱和点yj,逆向返回 if(j==n+1)break;end %找到X中标号为0 的点时结束, 获得M-增广路P k=k+1;end for(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0; %将匹配M 在增广路P 中出现的边去掉 else M(P(i,1),P(i,2))=1;end;end %将增广路P 中没有在匹配M中出现的边加入到匹配M中 break;end;end;end if(pd)break;end;end %假如X中所有有标号的点都已去掉了标记*, 算法终止 M %显示最大匹配M, 程序结束 利用可行点标记求最佳匹配算法的 MATLAB 程序代码如下： n=5; A=[3 5 5 4 1 2 2 0 2 2 2 4 4 1 0 0 1 1 0 0 1 2 1 3 3]; for(i=1:n)L(i,1)=0;L(i,2)=0;end for(i=1:n)for(j=1:n)if(L(i,1) for(i=1:n)for(j=1:n) %生成子图Gl if(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1; else Gl(i,j)=0;end;end;end ii=0;jj=0; for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;end if(ii)break;end;end %获得仅含Gl 的一条边的初始匹配M M(ii,jj)=1; for(i=1:n)S(i)=0;T(i)=0;NlS(i)=0;end while(1) for(i=1:n)k=1; 否则. for(j=1:n)if(M(i,j))k=0;break;end;end if(k)break;end;end if(k==0)break;end %获得最佳匹配M, 算法终止 S(1)=i;jss=1;jst=0; %S={xi}, T=φ while(1) jsn=0; for(i=1:jss)for(j=1:n)if(Gl(S(i),j))jsn=jsn+1;NlS(jsn)=j; %NL(S)= {v|u∈S,uv∈EL} for(k=1:jsn-1)if(NlS(k)==j)jsn=jsn-1;end;end;end;end;end if(jsn==jst)pd=1; %判断NL(S)=T? for(j=1:jsn)if(NlS(j)~=T(j))pd=0;break;end;end;end if(jsn==jst&pd)al=Inf;%如果NL(S)=T, 计算al, Inf 为∞ for(i=1:jss)for(j=1:n)pd=1; for(k=1:jst)if(T(k)==j)pd=0;break;end;end if(pd&al>L(S(i),1)+L(j,2)-A(S(i),j))al=L(S(i),1)+L(j,2)- A(S(i),j);end;end;end for(i=1:jss)L(S(i),1)=L(S(i),1)-al;end %调整可行点标记 for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end %调整可行点标记 for(i=1:n)for(j=1:n) %生成子图GL if(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1; else Gl(i,j)=0;end M(i,j)=0;k=0;end;end ii=0;jj=0; for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;end if(ii)break;end;end %获得仅含Gl 的一条边的初始匹配M M(ii,jj)=1;break else %NL(S)≠T for(j=1:jsn)pd=1; %取y∈NL(S)\T for(k=1:jst)if(T(k)==NlS(j))pd=0;break;end;end if(pd)jj=j;break;end;end pd=0; %判断y 是否为M的饱和点 for(i=1:n)if(M(i,NlS(jj)))pd=1;ii=i;break;end;end if(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj); %S=S∪{x}, T=T∪{y} else %获得Gl 的一条M-增广路, 调整匹配M for(k=1:jst)M(S(k),T(k))=1;M(S(k+1),T(k))=0;end if(jst==0)k=0;end M(S(k+1),NlS(jj))=1;break;end;end;end;end MaxZjpp=0; for(i=1:n)for(j=1:n)if(M(i,j))MaxZjpp=MaxZjpp+A(i,j);end;end;end M %显示最佳匹配M MaxZjpp %显示最佳匹配M的权, 程序结束 非诚勿扰男女最优组合 摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配 1、问题描述 《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。 2、模型建立 通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要 求，所以在本次模型建立过程中没有考虑这四位女嘉宾。 经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生为Y1，Y2，Y3，....Y20。X i与Y j之间连线，当且仅当它们所代表的男女双方满足彼此寻找另一半的某些要求，或者女生是男嘉宾选择的心动女生。由以上分析得到如图 2.1所示的二部图。 如何定义该二部图的权值：首先，每位男嘉宾的心动女生基本权值为1，其余女嘉宾的基本权值为0，然后根据男女嘉宾双方对对方的要求，在外貌、工作、性格、爱好、家庭五个方面基本相符就加1，差别很大就不加。得到如图2.2所示的加权图。 显然，为这些男女嘉宾找最优组合就转化为二部图（X，Y）寻找最大权匹配 图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%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) 1.1、prim算法: 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。 【Prim算法思想】 任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】连通所有城市的公路最小造价。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】50 原图 最小生成树 #include d[i]=INT_MAX; } d[f]=0; s=0; for(i=1;i<=n;i++) { mi=INT_MAX; for (j=1;j<=n;j++) if ((v[j]==false) && (d[j] 最短路算法及其应用 广东北江中学余远铭【摘要】 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。 【关键字】 最短路 【目录】 一、基本概念 (2) 1．1 定义 (2) 1．2简单变体 (2) 1．3负权边 (3) 1．4重要性质及松弛技术 (4) 二、常用算法 (5) 2．1 Dijkstra算法 (5) 2．2 Bellman-Ford算法 (7) 2．3 SPFA算法 (8) 三、应用举例 (10) 3．1 例题1——货币兑换 (10) 3．2 例题2——双调路径 (11) 3．3 例题3——Layout (13) 3．4 例题4——网络提速 (15) 四、总结 (18) 【正文】 一、基本概念 1．1 定义 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并 在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是没必要考虑的。 下面我们将阐明如何有效地解决这类问题。在最短路问题中，给出的是一 有向加权图G=(V ,E)，在其上定义的加权函数W:E →R 为从边到实型权值的映射。路径P=(v 0, v 1,……, v k )的权是指其组成边的所有权值之和： 11()(,)k i i i w p w v v -==∑ 定义u 到v 间最短路径的权为 {}{}min ():)w p u v u v v δυ→(,=∞ 如果存在由到的通路 如果不存在 从结点u 到结点v 的最短路径定义为权())w p v δυ=(,的任何路径。 在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。 边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示 时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。 1．2简单变体 单目标最短路径问题： 找出从每一结点v 到某指定结点u 的一条最短路 径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u 和v ，找出从u 到v 的一 条最短路径。如果我们解决了源结点为u 的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。 每对结点间的最短路径问题：对于每对结点u 和v ，找出从u 到v 的最短 路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。 数学建模10种常用算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问 题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行 编程的话，那一些数值分析中常用的算法比如方程组 求解、矩阵运算、函数积分等算法就需要额外编写库 函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关， 即使与图形无关，论文中也应该要不乏图片的，这些 图形如何展示以及如何处理就是需要解决的问题，通 常使用Matlab进行处 参数估计 C.F. 20世纪60年代,随着电子计算机的 。参数估计有多种方法，有最小二乘法、极大似然法、极大验后法、最小风险法和极小化极大熵法等。在一定条件下，后面三个方法都与极大似然法相同。最基本的方法是最小二乘法和极大似然法. 基本介绍 参数估计（parameter 尽可能接近的参数 误差 平方和 θ,使已知数据Y 最大,这里P(Y│θ)是数据Y P(Y│θ)。在实践中这是困难的，一般可假设P（Y│θ 关于最短路问题算法的一点思考 最短路问题，实际上是P95。也就是我们用一个算法解决SP问题时，就是在找这个加权图G中从s到t的P（s，t）中边权之和最小的P*(s,t). 由定义就可以看出，实际生活中经常有最短路问题的例子。例如： 实例1.某公司在六个城市s,t,a,b都有分公司，公司成员经常往来于它们之间，已知从Vi到Vj的直达航班票价由下述矩阵的第i行，第j列元素给出（∞表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。 图+矩阵 实例2.如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道。若有一批货物要从s号顶点运往t号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？ 图+矩阵 因此怎么样快速又精确的求解一个最短路问题就显得至关重要。下面我们来介绍几种解决SP问题的有效途径。 一、把求最短路问题转化为LP问题 P95 二、最短路问题的原始对偶算法：Dijkstra算法 Pdf最短路+课本P138 综上，即为Dijkstra算法，它的有效实施体现在：P161 对Dijkstra算法的一点思考： 1.关于Dijkstra算法，书中的例子定义了一个使用范围，即寻求有向图中，从一固定顶点到其余各点的最短路径。那么一个简单的推广就是在于，对于无向图或者混合图的情况Dijkstra算法还能否使用？答案应该是肯定的。也就是说，实例2中无论是单行道，双行道的情况都是可以应用Dijkstra算法进行求解的。 2. 作为学习图论的一名学生，Dijkstra算法的本质可以说就是在一个图中，进行标号,每次迭代产生一个永久标号, 从而生长一颗以s为根的最短路树,在这颗树上每个顶点与根s 节点之间的路径皆为最短路径. 3.Dijkstra算法明确要求权（费用）非负，这无疑会限制一些是实际生活中的例子进行求解，若出现的边权为负的情况，Dijkstra算法就要进行修改。并且，如果我们对Dijkstra算法进行编程，即使根据书中拟Algol语言的提示以我现有的水平也根本写不出Matlab的高级程序语言。但是有另外一种算法有效的避免了这个麻烦，它的逻辑更为简单，并允许网络中的弧有负权，能探测网络中负费用圈，与一般的原始对偶算法不同。 三、Floyd-Warshall算法 P164 并且，有一点比较吸引我的地方是在于Floyd-Warshall算法的逻辑较为简单，我可以跟据课本上拟Algol语言，编写出一部分Matlab的程序，但是因为编译程序的水平的限制，每次运行的时候都会出现不同的错误。在与计算数学的同学进行讨论的时候，因为他们偏重绘图而我们偏重优化，导致也为得出有效的解决措施。 二分图的最优匹配（KM算法） KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。 基本原理 该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T } 图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma) Dijkstra 算法： 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量 pb 、1index 、2index 、d 分别用 来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ? ?=顶点未标号当第顶点已标号 当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb) 图论之最短路 一、求最短路方法（对于一个包含环的图） 1、Dijkstra 2、Bellman-ford 3、SPFA 4、Floyd 二、Dijkstra思想（求单源点最短路，不含负边权） 1、设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v 到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2、Dijkstra步骤 （1）初始时，S只包含源点，即S＝v，距离为0。U包含除v外的其他顶点，U 中顶点u距离为边上的权； （2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）； （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值为经过顶点k的值（松弛操作）； （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 3、Dijkstra两种实现方法 （1）邻接矩阵+找最小边 （2）邻接表+优先队列 关键：松弛操作 if(d[v]>d[u]+e[u][v].w) d[v]=d[u]+e[u][v].w 4、Dijkstra 稠密图的邻接矩阵 for(int i=0;i 图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到 j v 的权 ij w =∞ 。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在1i v +，使1()min{()}i l v l v +=，v S ∈； ⑤ 1{}i S S v += ，1{}i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v - 是从1v 到n v 的最短路径，则121n v v v - 也必然是从1v 到1n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到 j v 的权 ij w ，若i v 到 j v 无边，则 realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma) 图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1) for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>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;end for(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;e nd if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量 精心整理 图论算法matlab实现 求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for for(i=1:n)for(j=1:n)if(C(i,j)>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;end for(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;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用 最优化理论 一、最优化理论概述 优化是从处理各种事物的一切可能的方案中，寻求最优的方案。优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化问题。优化一语来自英文Optimization，其本意是寻优的过程；优化过程：是寻找约束空间下给定函数取极大值（以max表示)或极小(以min表示)的过程。优化方法也称数学规划，是用科学方法和手段进行决策及确定最优解的数学。在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。 最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。 最优化理论与方法作为一个重要的数学分支，它所研究的就是在众多的方案中怎么能找到最优、最好的方案。由于科学技术与生产技术的迅速发展，尤其是计算机应用的不断扩大，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此，发展成了一种新的科学。最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：连续优化：包括线性规划、非线性规划、全局优化、锥优化等；离散优化：网络优化、组合优化等；和近年来发展迅速的智能优化等。 一般而言，最优化问题的求解方法大致可分为4类：1)解析法：对于目标函数及约束条件具有简单而明确的数学表达式的最优化问题，一般都可采用解析法。在解决实际问题时，由于描述实际问题的解析形式的数学表达式很难找到，因此，这种表达式则缺 《图论及其算法》 --最短路问题 学院：通信学院 姓名：周旋 学号： S110131133 指导老师：陈六新 摘要 图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这些图形通常用来描述某些事物之间的特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。通过对《图论及其应用》中最短路问题的深入学习，本文利用Dijkstra算法来解决日常生活中寻找最短路的问题。同时也是对本学期学习知识的巩固。 关键词：最短路径 Dijkstra算法迭代 Abstract Graph theory is a branch of mathematics, it studies the object of picture. Graph theory graph is given by the number of points and lines connecting the two points of the graphic form. These graphics are often used to describe a specific relationship between certain things. And with the point on behalf of things, with the line connecting the two points that have a corresponding relationship between two things. Through the "Graph Theory and Its Applications," in-depth study of the shortest path problem. In this paper, we use The Dijkstra's algorithm not only to solve everyday life to find the shortest path problem, but also for the consolidation of the semester to learn the knowledge. Keyword: shortest path Dijkstra's algorithm Iteration Floyd最短路径算法 在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层的时候好像也遇到过这个问题，记不请了... 但是书本上一律采取的是Dijkstra算法，通过Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味，采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下： 如果有一个矩阵D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序，通过这个距离矩阵D，把任意两个城市之间的最短与其行径的路径找出来。 我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n 是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i 到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的话，会发现是有问题的。 for(int i=0; i 算法图论（Graph Theoretic Algorithms） 第一部分：区间图、弦图、相似图、完美图 本书英文版共29讲，第一部分共12讲，系译者学习的同时为备以后查阅复习之便作的翻译，内容基本忠实于原著，且大部分是直译，同时加入了译者的少许想法，并补上了少部分略去的证明过程（限于译者的水平只能证明一些力所能及的证明）。 第1讲是概论导读；第2到10讲比较详细地介绍了区间图、弦图及其相关的性质、算法（包括证明）以及延伸内容，其中第7到9讲涉及相似图的一些内容，部分定理尚未证明；第11、12讲介绍完美图、相交图及其部分特例，侧重于介绍性，概念结论较多但证明较少，可以作为知识性的阅读。 《尚为解决的问题》是译者翻译学习过程中遇到的一些不懂的问题，原文中未给出详细证明，而译者目前还无法自己证明的，这些在译文中将用粗括号扩出。各路高手如有知道方法的情与译者联系，不胜感激！ 复旦附中葛潇 第一讲、概论 本讲对这门课程的主要议题进行了大致的介绍。 1．概念 这门课程涉及了一些特殊的图以及这些图上某些已经得到改进及仍未解决的问题。 为了解我们所说的内容，我们必须回顾一些特殊图中的概念、算法、复杂度分析及NP —HARD问题。在这门课中对些将不作深入，我们假设读者以对这些有所了解。 2．一些图的分类 下面我们将给出这门课程中将涉及的一些图的形式。在以后的各讲中将进行深入的分析。 z区间图（Interval graphs）：如果一个图能用一些区间的intersection graph表示，那么这个图称为区间图。更准确地说，给定一系列区间，将其中每个区间看作一个顶点，两个顶点间有边，当且仅当这两个点所代表的区间相交。一个图是区间图，当且仅当它能通过以上方法构造出来。（见图1） 图1：一些区间及它们所构成的区间图 我们同时学习各种相关的图，例如弦图和完美图。这部分的主要参考是[Gol80]。 z树（Trees）：一个图是一颗树，当且仅当它是连通的，并且没有环。我们将同样学习有关的图，例如partial k-trees. 这部分的主要参考是[Bod93]。 z平面图（Planar graphs）：一个图如果能画在二维平面上，且各边没有交点，则该图称为平面图。注意每个树都是平面图，但反之却不一定。我们将同样学习有关的图，例如outer-planar graphs 和 series-parallel graphs（混联图）。这部分的主要参考是[NC88]。 本课程中除特别说明，一般所指的图都是简单的、连通的，且至少有两个顶点（或是图有意义的最少顶点）。显然这不会影响大多数算法的适用性。 同时，一般给出的图都是无向图，虽然有时我们为了设计算法人为地加上方向。 3．一些问题 下面是我们将学习的一些问题，以及它们在一些特殊图上的复杂度。 z最大独立集（Maximum Independent Set）：这是著名的NP难题。但在区间图中，最大独立集问题能够在O（N＋M）时间内解决，同时在树上可以在线性时间内解决，但对于平面图这仍是NP难题。 z最大割(Maximum Cut)：图G＝（V，E）上的一个割将该图的顶点分成两个子集：V＝A＋B。更准确地说，给定一种顶点划分，一个割是哪些一个端点在A中，另一个在B 中的边组成的集合。最大割问题是寻找一种顶点划分方式，使得对应割集中的边数最多。 同样也有最小割问题。最小割问题用最大流的方法可以在多项式时间内解决，但最大割问题是NP难题。但在平面图上最大割问题是多项式级的；在树上，最大割问题是平凡图论最优化算法
图论算法及其MATLAB程序代码
图论算法详解(C++版)
最短路算法[1]
数学建模10种常用算法
关于最短路问题算法的一点思考
算法学习：图论之二分图的最优匹配(KM算法)
图论算法及matlab程序的三个案例
图论算法
图论之 最短路
图论算法及matlab程序的三个案例
maab图论程序算法大全
matlab图论程序算法大全
最优化理论
图论及其算法
最短路算法程序
算法图论
相关主题
文本预览