非诚勿扰男女最优组合
摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。
关键词：非诚勿扰，最大权匹配
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）寻找最大权匹配
图 2.1
图 2.2
3、模型求解
本模型用匈牙利算法来进行求解。其中S表示交错树中属于X的顶点集；T表示交错树中属于Y的顶点集；F（Y）表示Y的父亲；N（S）表示S的邻域；A(X i)表示X i的邻接点集；W ij表示X i Y j边上的权。
求解步骤如下：
1)给出初始标号：
L(X1)=max{1,2,0,0,0,2,0,0,0,0,2,2,0,0,1,0,0,0,0,0}=2 L(X2)=max{0,0,3,0,3,0,0,0,0,0,0,3,0,1,0,1,0,2,0,0}=3 L(X3)=max{0,4,0,0,0,5,2,2,3,0,4,0,1,0,0,0,5,0,1,0}=5 L(X4)=max{0,0,0,2,0,0,0,0,0,4,0,0,0,0,3,0,0,0,0,4}=4 L(Y1)=L(Y2)=L(Y3)=L(Y5)=L(Y6)=L(Y7)=L(Y8)=L(Y9)=L(Y10)
=L(Y11)=L(Y12)=L(Y13)=L(Y14)=L(Y15)=L(Y16)=L(Y17)=L(Y18)=L(Y20) =L(Y21)=L(Y24)=0
2)求出A Gl(X i)及匹配M：
A Gl(X1) = {Y2 ,Y7 ,Y12 ,Y13 } A Gl(X2) = {Y3 ,Y6 ,Y13 }
A Gl(X3) = {Y7 ,Y18} A Gl(X4) = {Y11 ,Y24}
对应等子图G l如图3.1所示，求得匹配M，M={X1Y13，X3Y7，X4Y24}。如图3.1黑线所示
。x1。X2。X3。X4
。。。。。。。。。
Y2 Y3 Y6 Y7 Y11 Y12 Y13 Y18 Y24
图 3.1
3）X2是非渗透点，u=X2 ,用匈牙利算法求出以u为根的M交错树得：S={X1，X2 ，X3}, T={Y7，Y13}，N(S)={Y2，Y3，Y6，Y7，Y12，Y13，Y18}。因N Gl(S)≠T，找一点Y3 ∈A(X2)-T, F(Y3)←X2。因Y3 是M非渗透点，故得一条M可增长路径P = X2Y3
E（P）= {X2Y3}
因而得到新匹配
M = M△E（P）= {X1Y13，X3Y7，X4Y24, X2Y3}
4）至此已渗透X中所有顶点，M即为最大权匹配。
此时得到的男女最优组合为：1号男嘉宾吴楷与13号女嘉宾肖俊，吴楷是一个帅气、认真、努力、爱好中国古文化但不是很擅长交际的专一型外国男生，对另一半的要求是活波、喜欢冒险、运动的女
生，与13号女嘉宾要求男方要做到诚实相待、善良不撒谎、会照顾人相符，相处之后女生活波的一面也会带动男生；2号男嘉宾张涛与3号女嘉宾张馨予，双方都属于自己创业，也都有一定的成就，在生活中有很多话题、很多共鸣，而且女生属于胆大心细、温柔不强势类型，是男嘉宾心中的理想型，女生希望无论恋爱还是结了婚，对方都不要有欺骗，更不要轻易放弃，发生任何事情都要坚持，婚后不介意和对方家人住一起，与男嘉宾工作能力强、不善交际、踏实肯干十分相符；3号男嘉宾张凡帆与7号女嘉宾魏鸾莹，男嘉宾成熟、热爱生活，有梦想、有追求，与女嘉宾希望对方尊重家庭，有责任感、可以分享周遭的许多事情十分相符，而且两人在节目中互动也挺多，更幸运的是两人还在同一城市。4号男嘉宾丁腾与24号女嘉宾顾欣伟，男嘉宾年少有为，但有点大男子主义，女嘉宾属于温婉、居家类型，而且为男嘉宾一路留灯到最后，需要很大勇气，很有缘分的是两人穿的是情侣装。
但最后得到的最大权匹配也只是建立在本模型中理论上的，与节目最终的结果还是有区别的，最后只有最大权匹配中的两对牵手成功。
附加题：校园导游任意两景点求最短路径
方案：校园导游为用户提供平面图中任意两点间的问路查询，即查询任意两个景点间的最短路径，旨在为用户的旅游大大提高效率。
用无向网表示学校的平面图，设计了该平面图的存储结构，并应用Dijkstra算法实现了查询图中任意两个景点间的最短路径的功能，为用户熟悉校园环境提供了方便。
算法描述：
s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]。
初始化：源的距离dist[s]设为0，其他的点距离设为无穷大(实际程序里设成-1了)，同时把所有的点的状态设为没有扩展过。
循环n-1次：
1) 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
2) 对于每个与u相邻的点v，如果
dist[u]+G.edges[u][v] 3) 结束。此时对于任意的u，dist[u]就是s到u的距离。 景点1到各点最短路径 邻接矩阵如图1所示 {0 340 320 ∞∞∞∞∞∞∞∞ 360} { 0 150 600 ∞∞∞∞∞∞∞∞ } { 0 ∞∞∞ 300 ∞∞∞∞ 150} { 0 250 ∞∞ 430 ∞∞∞∞ } { 0 180 ∞∞∞∞∞∞ } W = { 0 100 ∞ 290 ∞∞∞ } { 0 ∞∞∞ 150 ∞ } { 0 430 ∞∞∞ } { 0 150 ∞∞ } { 0 450 ∞ } { 0 380} { 0 } 图 1 Dijkstra各次迭代各变量值的变化情况如下表1所示 利用算法的父点追踪便可得到从U1到其余各点的最短路径。 部分代码： void Dijkstra(int v, int w) { int dist[MAXV], path[MAXV]; //dist[]记录顶点到其他各点的权值，path[]记录源点到其余各点是否有路径 int s[MAXV]; //s[]记录经过的顶点 int mindis, i, j, u; for(i = 0; i < G.vexnum; i ++) { dist[i] = G.edges[v][i]; //距离初始化 s[i] = 0; //s[]置空 if(G.edges[v][i] < INF) //路径初始化 path[i] = v; else path[i] = -1; } s[v] = 1; path[v] = 0; //源点编号v放到s中 //循环直到所有顶点的最短路径都求出 for(i = 0; i < G.vexnum; i ++){ mindis = INF; //mindis置最小长度初值 for(j = 0; j < G.vexnum; j ++){ if(s[j] == 0 && dist[j] < mindis){ u = j; mindis = dist[j]; } } s[u] = 1; for(j = 0; j < G.vexnum; j ++){ if(s[j] == 0){ if(G.edges[u][j] < INF && dist[u] + G.edges[u][j] < dist[j]) { dist[j] = dist[u] + G.edges[u][j]; path[j] = u; } } } } Dispath(dist, path, s, v, w); } 图论算法及其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 的最短 路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。 图论最短路径问题 在消防选址中的应用 【摘 要】 最短路径问题是图论解决的典型实际问题之一，可用来解决管路铺设、线路 安装、厂区布局和设备更新等实际问题。介绍了图论最短路径问题及其算法，并应用图论最短路径问题的分析方法，解决城市消防站的选址问题。 【关键词】 最短路径；Floyd 算法；消防 1 引言 图论是运筹学的一个重要分支，旨在解决离散型的优化问题，近年来发展十分迅速。在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。图论中的“图”，并不是通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统。也就是说，几何图形是表述 物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系。它是数学中经常采用的抽象直观思维方法的典型代表。 2 图论基本概念 2.1 图的定义 有序三元组),,(?E V G =称为一个图，其中： (1)),,,(21n V V V V =是有穷非空集，称为顶点集，其元素叫做图的顶点； (2)E 称为边集，其元素叫做图的边； (3)?是从边集E 到顶点集V 的有序或者无序对集合的影射，称为关联函数。 2.2 图的分类 在图G 中，与V 中的有序偶),(j i V V 对应的边e 称为图的有向边(或弧)，而与V 中顶点的无序偶对应的边e 称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为 ),(E V G =；每一条边都是有向边的图叫做有向图，记为),(E V D =；既有无向边又有有 向边的图叫做混合图。 2.3 权 如果图G 中任意一条边),(j i V V 上都附有一个数ij W ，则称这样的图G 为赋权图， ij W 称为边),(j i V V 上的权。 关于最短路问题算法的一点思考 最短路问题，实际上是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的程序，但是因为编译程序的水平的限制，每次运行的时候都会出现不同的错误。在与计算数学的同学进行讨论的时候，因为他们偏重绘图而我们偏重优化，导致也为得出有效的解决措施。 图论之最短路 一、求最短路方法（对于一个包含环的图） 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 图论实验三个案例 单源最短路径问题 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) 图论算法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%计算最小费用 《图论及其算法》 --最短路问题 学院：通信学院 姓名：周旋 学号： 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 图论实验三个案例 单源最短路径问题 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) 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 最短路法MATLAB 程序 例1： 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ??????????????????∞∞∞∞∞∞ 05525251055010202525100102040 2010015252015050102540500 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、 2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ??=顶点未标号当第顶点已标号当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下： 程序一： clc,clear a=zeros(6); %邻接矩阵初始化 a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; %将矩阵数据对称赋予矩阵 a(find(a==0))=inf; %找到0值并赋值为inf pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0; temp=1; %最新的P标号的顶点 while sum(pb) 算法图论（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难题。但在平面图上最大割问题是多项式级的；在树上，最大割问题是平凡 1、最优连线问题 （最优连线问题）我国西部的SV地区共有1个城市（标记为1）和9个乡镇（标记为2--10）组成，该地区不久将用上天然气，其中城市1含有井源.现要设计一供气系统，使得从城市1到每个乡镇（2--10）都有一条管道相边，并且铺设的管子的量尽可能的少.图7-9给出了SV 地区的地理位置图，表7-7给出了城镇之间的距离. Lingo程序如下：model: data: n=10; enddata sets: cities/1..n/: F; roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10 /: D, P; endsets data: D= 6 5 3 6 9 7 5 11 9 1 8 7 5 4 10 5 9; enddata F(n)=0; @for(cities(i) | i #lt# n: F(i)=@min(roads(i,j): D(i,j)+F(j)); ); @for(roads(i,j): P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0) ); end 结果： 2、任意两点间的最短路程问题： 某公司在六个城市c1, …,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵中的(i,j) 位置上。（∞表示无直接航路），请帮助该公司设计一张任意两城 市间的票价最便宜的路线表。 0 50 ∞40 25 10 50 0 15 20 ∞25 ∞15 0 10 20 ∞ 25 ∞20 10 0 55 10 25 ∞25 55 0 Lingo程序如下： 图论中的概念及重要算法 常州一中林厚从 chi、图论中的基本概念 一、图的概念 简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph= （V，E）, V是点（称为"顶点”）的非空有限集合，E是线（称为"边”）的集合，边一般用（V x，V y）表示，其中V x，V y属于V。 图（A）共有 4 个顶点、5 条边，表示为：V={v i, V2, V3, V4}，E={（V i，V2），（V i，V3）， （V i，V4），（V2，V3），（V2，V4）} 二、无向图和有向图 如果边是没有方向的，称此图为“无向图” ，如图（A）和图（C）,用一对圆括号表示无向边，如图（A）中的边（V i，V2），显然（V x，▼『）和（V y，V x）是两条等价的边，所以在上面E 的集合中没有再出现边（V2，V i）。 如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边＜V i，V2＞。把边＜v x，v y＞中V称为起点，v y称为终点。显然此时边w，V y＞与边＜V y，V x＞是不同的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。 图（B）表示为：V={V i，V2，V3}，E={＜V i，V2＞，＜V i，V3＞，＜ V2，V3＞，＜V3，V2＞} 如果两个顶点U V之间有一条边相连，则称U V这两个顶点是关联的。 三、带权图 一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的图称为带权图，也称为网（络）。 四、阶 图中顶点的个数称为图的阶。图（A）、图（B）、图（C）的阶分别为4、3、5。 五、度 图中与某个顶点相关联的边的数目，称为该顶点的度。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。图（A）中顶点V i，V2是奇点，V3，V4是偶点。 图论算法-最大流算法和最大匹配算法 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);图论算法及其MATLAB程序代码
图论算法详解(C++版)
最短路算法[1]
图论中最短路径问题
关于最短路问题算法的一点思考
图论之 最短路
图论算法及matlab程序的三个案例
图论算法
maab图论程序算法大全
matlab图论程序算法大全
图论及其算法
图论算法及matlab程序的三个案例
最短路算法程序
图论最短路MATLAB程序
算法图论
图论算法实例
图论中的概念及重要算法
图论算法-最大流算法和最大匹配算法
相关主题
文本预览