for(int j=1;j<=n;j++) if( !used[j] && tmin > dis[j] ){ tmin = dis[j]; k = j; } used[k] = 1; for(int j=1;j<=n;j++) if( dis[k] + map[k][j] < dis[j] ) dis[j] = dis[k] + map[k][j]; } printf(\,dis[n]); } /* 求1到N的最短路,dis[i] 表示第i个点到第一个点的最短路 By Ping*/ 还有其他算法： Floyd-Warshall算法 Bellman-Ford算法 Johnson算法 实例： 某公司在六个城市c1,c2,?,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的（?表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最(i,j)位置上。便宜的路线图。 ?0?50?????40?25??1050?402510?01520?25??1501020??? 201001025??2010055??25?25550?用矩阵an?n（n为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、index2、
d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量
?1当第i顶点已标号； pb(i)??0当第i顶点未标号?index2(i) 存放始点到第i点最短通路中第i顶点前一顶点的序号； d(i) 存放由始点到第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) d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)>=2 index=index(1); end index2(temp)=index; end d, index1, index2 运行结果为： d = 0 35 45 35 25 10 index1 = 1 6 5 2 4 3 index2 = 1 6 5 6 1 1 即： d（最短通路的值） index1（标号顶点顺序） index2（标号顶点索引） 0 1 1 35 6 6 45 5 5 35 2 6 25 4 1 10 3 1 2、 网络流 （1）含义的理解 网络流（network flows）是图论中的一种理论与方法，研究网络上的一类最优化问题 。 （2）历史及应用 1955年 ，T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D＝ （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起 点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。 最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。 最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题 ，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。 目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。 （3）算法的实现 Edmonds-Karp 算法 建立在Ford-Fulkerson方法上的增广路算法,与一般的Ford-Fulkerson算法不同的是,它用广度搜索实现对增广路的寻找. 以下为代码: int n; long int c[128][128]; long maxflow(int s, int t) { int p, q, queue[128], u, v, pre[128]; long int flow, aug; flow = 0; while(true) { memset(pre, -1, sizeof(pre)); for(queue[p = q = 0] = s; p <= q; p++) { u = queue[p]; for(v = 0; (v < n) && (pre[t]) < 0; v++) { if((c[u][v] > 0) && (pre[v] < 0)) { pre[v] = u; queue[++q] = v; } } if(pre[t] >= 0) { break; } } if(pre[t] < 0) { break; } aug = 0x7fff; for(u = pre[v = t]; v != s; (v = u), (u=pre[u])) { if(c[u][v] < aug) { aug = c[u][v]; } } for(u = pre[v = t]; v != s; (v = u), (u = pre[u])) { c[u][v] -= aug; c[v][u] += aug; } flow += aug; } return flow; } 3、 二分图 （1） 含义的理解 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 2、相关应用 作为一种数学模型，二分用途是十分有用的，许多问题可以用它来刻划。例如“资源匹配”、“工作安排”、“人员择偶”等等。而这就需要考虑匹配问题。 匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 而二分图最大匹配可以用最大流或者匈牙利算法。 最大流在网络流中有介绍。 匈牙利算法为：（资料：百度百科） 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理（此定理使用于组合问题中。二部图G中的两部分顶点组成的集合分别为X, Y, Z,={X1, X2, X3,X4, .........,Xm} , Y={y1, y2, y3, y4 , .........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是： X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)）中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 算法的思路： 不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条\交错轨\也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行\反色\容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路. 资料来源： http://www.nocow.cn/index.php/?????????????3? 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。 增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。（M为一个匹配） 由增广路的定义可以推出下述三个结论： 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 2. P经过取反操作可以得到一个更大的匹配M’。 3. M为G的最大匹配当且仅当不存在相对于M的增广路径。 用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出) 算法轮廓： 1. 置M为空 2. 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M 3. 重复(2)操作直到找不出增广路径为止 程序清单： const maxm=200; maxn=200; var i,j,k,m,n:longint; g:array[1..maxm,1..maxn]of boolean; y:array[1..maxn]of boolean;
数学建模十大经典算法
