图论最短路MATLAB程序

图论中最短路算法与程序实现图论中的最短路问题(包括无向图和有向图)是一个基本且常见的问题。

主要的算法有Dijkstra 算法和Floyd 算法。

Dijkstra 算法是求出指定两点之间的最短路，算法复杂度为 Floyd 算法是求出任意两点之间的最短路，算法复杂度为 2()O n 3()O n1.Dijkstra算法2. Floyd算法算法程序(Matlab)为：for k=1:nfor i=1 :nfor j=1:nt=B(i,k)+B(k,j);if t<B(i,j) B(i,j)=t; end endendend起点终点距离起点终点距离起点终点距离12400718160151725013450892001617140243008152851618130221230910180172724024714010111501819204346001015160182518045210111214019201404193101114130192417556230121320020211805720013344002024190673201415190212230068340142619021232707817015161702147350表1 各点距离(m)实例：已知50个点之间相互连接信息见表1及续表。

求最短距离矩阵续表1 各点距离(m)起点终点距离起点终点距离起点终点距离22441602229313640190 22452702230313738135 22481802230423839130 23242402330433941310 23292102331324041140 23302902331364050190 23441502331504250200 24251702432334344260 24281302432354345210 26271402632364546240 26343202633344648280 27281902735374849200 2829260283639n=50; %Matlab实现的Floyd算法A=zeros(n,n);for i=1:nfor j=1:nif(i==j) A(i,j)=0;else A(i,j)=100000;endendend %赋直接距离信息A(1,2)=400;A(1,3)=450; A(2,4)=300;A(2,21)=230; A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200; A(6,7)=320; A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285; A(9,10)=180; A(10,11)=150; A(10,15)=160; A(11,12)=140; A(11,14)=130; A(12,13)=200; A(13,34)=400;A(14,15)=190;A(14,26)=190; A(15,16)=170; A(15,17)=250; A(16,17)=140;A(16,18)=130; A(17,27)=240; A(18,19)=204; A(18,25)=180; A(19,20)=140; A(19,24)=175; A(20,21)=180; A(20,24)=190; A(21,22)=300; A(21,23)=270; A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240; A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130; A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190; A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260; A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210; A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130; A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260; A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;for j=1:nfor i=1:j-1A(j,i)=A(i,j); %使矩阵对称endendB=A;%利用Floyd算法计算最短距离矩阵for k=1:nfor i=1 :nfor j=1:nt=B(i,k)+B(k,j);if t<B(i,j) B(i,j)=t; endendendend %输出距离矩阵到文件fid=fopen('distance.txt','w'); for i=1:nfor j=1:nfprintf(fid,'%4d ',B(i,j)); endfprintf(fid,'\n');endfclose(fid);谢谢！。

function [c0,c,path0,path]=dijkstra(s,t,C,flag)% Use the Dijkstra's algorithm to find the shortest path from% s to t and can also find the shortest path between s and all% the other points.% Reference: Graph Theory with Applications by J. A. Bondy and% U. S. R. Murty.% Input -- s is the starting point and also is the point s.% -- t is the given terminal point and is the point t.% -- C \in R^{n \times n}is the cost matrix, where% C(i,j)>=0 is the cost from point i to point j.% If there is no direct connection between point i and% j, C(i,j)=inf.% -- flag: if flag=1, the function just reports the% shortest path between s and t; if flag~=1, the% function reports the shortest path between s and t,% and the shortest paths between s and other points.% Output -- c0 is the minimal cost from s to t.% -- path0 denotes the shortest path form s to t.% -- c \in R{1\times n} in which the element i is the% minimal cost from s to point i.% -- path \in R^{n \times n} in which the row i denotes% the shortest path from s to point i.% Copyright by MingHua Xu(徐明华), Changhzou University, 27 Jan. 2014. s=floor(s);t=floor(t);n=size(C,1);if s<1 || t < 1 || s > n || t > nerror(' The starting point and the terminal point exceeds the valid range');endif t==sdisp('The starting point and the terminal point are the same points');endlabel=ones(1,n)*inf;label(s)=0;S=[s];Sbar=[1:s-1,s+1:n];c0=0;path=zeros(n,n);path(:,1)=s;c=ones(1,n)*inf;parent=zeros(1,n);i=1; % number of points in point set S.while i<n% for each point in Sbar, replace label(Sbar(j)) by% min(label(Sbar(j)),label(S(k))+C(S(k),Sbar(j)))for j=1:n-ifor k=1:iif label(Sbar(j)) > label(S(k))+C(S(k),Sbar(j))label(Sbar(j))=label(S(k))+C(S(k),Sbar(j));parent(Sbar(j))=S(k);endendend% Find the minmal label(j), j \in Sbar.temp=label(Sbar(1));son=1;for j=2:n-iif label(Sbar(j))< temptemp=label(Sbar(j));son=j;endend% update the point set S and SbarS=[S,Sbar(son)];Sbar=[Sbar(1:son-1),Sbar(son+1:n-i)];i=i+1;% if flag==1, just output the shortest path between s and t.if flag==1 && S(i)==tson=t;temp_path=[son];if son~=swhile parent(son)~=sson=parent(son);temp_path=[temp_path,son];endtemp_path=[temp_path,s];endtemp_path=fliplr(temp_path);m=size(temp_path,2);path0(1:m)=temp_path;c_temp=0;for j=1:m-1c_temp=c_temp+C(temp_path(j),temp_path(j+1));endc0=c_temp;path(t,1:m)=path0;c(t)=c0;returnendend% Form the output resultsfor i=1:nson=i;temp_path=[son];if son~=swhile parent(son)~=sson=parent(son);temp_path=[temp_path,son];endtemp_path=[temp_path,s];endtemp_path=fliplr(temp_path);m=size(temp_path,2);path(i,1:m)=temp_path;c_temp=0;for j=1:m-1c_temp=c_temp+C(temp_path(j),temp_path(j+1));endc(i)=c_temp;c0=c(t);path0=path(t,:);endreturn。

图论实验三个案例单源最短路径问题 1.1 Dijkstra 算法Dijkstra 算法是解单源最短路径问题的一个贪心算法。

其基本思想是，设置 一个顶点集合S 并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S 当且 仅当从源到该顶点的最短路径长度已知。

设 v 是图中的一个顶点，记l(v)为顶点 v 到源点V 1的最短距离，V i,V jV ，若(V i,V j)E ，记“到百的权w 。

Dijkstra 算法：① S {V J I(V J 0 ； V V {可 1(V ) i i S V {V J ；J7JJJ7②S，停止，否则转③；l(v) min{ l(v) , d(V j ,v)}V j S④ 存在Vi 1，使l (V i l) min{l(V)}，V S ；⑤SSU{v i 1}S S {v i 1}i i 1实际上，Dijkstra 算法也是最优化原理的应用：如果V 1V 2LV n1Vn是从V1到Vn的最短路径，贝UV 1V 2L Vn1也必然是从V1到Vn 1的最优路径。

在下面的MATLA 实现代码中，我们用到了距离矩阵，矩阵第 i 行第j 行元 素表示顶点Vi到Vj的权Wj，若v 到V j无边，则W ijrealmax，其中realmax 是 MATLA 常量，表示最大的实数(1.7977e+308)function re=Dijkstra(ma)%用Dijkstra 算法求单源最短路径%俞入参量ma是距离矩阵%输出参量是一个三行n 列矩阵，每列表示顶点号及顶点到源的最短距离和前顶点n=size(ma,1);% 得到距离矩阵的维数s=ones(1,n);s(1)=0;% 标记集合S和S 的补r=zeros(3,n);r(1,:)=1:n;r(2,2:end)=realmax;% 初始化for i=2:n;% 控制循环次数mm=realmax;for j=find(s==0);% 集合S中的顶点for k=find(s==1);% 集合S补中的顶点if(r(2,j)+ma(j,k)<r(2,k))r(2,k)=r(2,j)+ma(j,k);r(3,k)=j;endif(mm>r(2,k))mm=r(2,k);t=k;endendends(1,t)=0;%找到最小的顶点加入集合Send re=r;1.2动态规划求解最短路径动态规划是美国数学家 Richard Bellman 在1951年提出来的分析一类多阶 段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控 制工程等方面均有着广泛的应用。

最短路径算法matlab代码最短路径算法是计算两点之间最短路程的算法。

这个问题可以转化为图论中的最短路径问题，目前有多种解法，其中比较常用的就是迪杰斯特拉算法和弗洛伊德算法。

本文将以迪杰斯特拉算法为例，介绍一下最短路径算法的matlab实现。

迪杰斯特拉算法迪杰斯特拉算法是用来解决有向带权图中单源最短路径问题的一种贪心算法。

该算法通过维护一个距离集合，逐步扩展最短路径，直至到达终点或者所有路径均已扩展完毕。

具体算法流程如下：1. 初始化距离集合，将距离集合中除起点外所有点的距离设置为无穷大，将起点的距离设置为0。

2. 从距离集合中选择距离最小的点v，将v加入已扩展集合中。

3. 遍历v的所有邻居节点，将v到邻居节点的距离d与邻居节点原有的距离比较，若d小于原有距离，则将邻居节点的距离更新为d。

4. 重复以上步骤，直至所有点均已加入已扩展集合中。

matlab代码实现在matlab中实现迪杰斯特拉算法，需要用到矩阵来描述整个图。

用一个N*N的矩阵表示图中各节点之间的距离，例如：```G = [ 0, 4, 2, Inf, Inf;Inf, 0, 1, 5, Inf;Inf, Inf, 0, Inf, 3;Inf, Inf, Inf, 0, 1;Inf, Inf, Inf, Inf, 0 ];```其中Inf表示节点间没有连接。

然后，将距离集合D初始化为一个1*N 的向量，D(i)表示起点到节点i的距离。

对于起点，其距离应该为0。

```D = [0 Inf Inf Inf Inf];```接下来，用一个1*N的向量S来表示已经扩展过的节点。

一开始，S 中只有起点。

```S = [1];```接下来就可以实现算法了。

迭代遍历S中的所有节点，更新其邻居节点的距离，然后将距离最小的邻居节点加入S中。

具体实现代码如下：```for i = 1:N-1minDis = Inf;for j = 1:Nif ~ismember(j, S) % 如果节点j不在已扩展集合中if D(j) < minDisu = j;minDis = D(j);endendendS = [S u];for v = 1:Nif ~ismember(v, S) % 如果节点v不在已扩展集合中if G(u, v) ~= Inf % 如果u和v之间存在连接if D(u) + G(u, v) < D(v) % 如果从起点到u节点再到v节点的距离小于v原有距离D(v) = D(u) + G(u, v); % 更新v的距离endendendendend```完整代码将上述代码整合成一个函数，得到完整的matlab代码实现。

matlab dijkstra算法求解最短路径例题摘要：一、Dijkstra 算法简介1.Dijkstra 算法背景2.Dijkstra 算法原理二、MATLAB 实现Dijkstra 算法求解最短路径1.创建图对象2.计算最短路径3.可视化结果三、Dijkstra 算法应用示例1.例题描述2.解题步骤3.结果分析正文：一、Dijkstra 算法简介Dijkstra 算法是一种经典的图论算法，用于计算图中两个节点之间的最短路径。

它是由荷兰计算机科学家Edsger W.Dijkstra 于1956 年提出的，其基本思想是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

可以用堆优化来提高效率。

二、MATLAB 实现Dijkstra 算法求解最短路径1.创建图对象首先，我们需要使用MATLAB 的graph 函数创建一个图对象，指定节点和边的信息。

例如，我们创建一个简单的图，包含4 个节点和3 条边：```matlabG = graph(4, 3);```其中，4 表示图中有4 个节点，3 表示图中有3 条边。

2.计算最短路径接下来，我们可以使用MATLAB 的shortestpath 函数计算两个节点之间的最短路径。

例如，我们计算节点1 到节点3 的最短路径：```matlabSP = shortestpath(G, 1, 3);```3.可视化结果最后，我们可以使用MATLAB 的plot 函数将最短路径可视化。

例如，我们绘制节点和边以及最短路径：```matlabplot(G, SP);```三、Dijkstra 算法应用示例以下是一个使用Dijkstra 算法求解最短路径的例题：在一个图中，有4 个节点和3 条边，如下所示：```1 --2 -- 3| /| /| /| /|/4```请问，节点1 到节点4 的最短路径是多少？。

function [c0,c,path0,path]=dijkstra(s,t,C,flag)% Use the Dijkstra's algorithm to find the shortest path from% s to t and can also find the shortest path between s and all% the other points.% Reference: Graph Theory with Applications by J. A. Bondy and% U. S. R. Murty.% Input -- s is the starting point and also is the point s.% -- t is the given terminal point and is the point t.% -- C \in R^{n \times n}is the cost matrix, where% C(i,j)>=0 is the cost from point i to point j.% If there is no direct connection between point i and% j, C(i,j)=inf.% -- flag: if flag=1, the function just reports the% shortest path between s and t; if flag~=1, the% function reports the shortest path between s and t,% and the shortest paths between s and other points.% Output -- c0 is the minimal cost from s to t.% -- path0 denotes the shortest path form s to t.% -- c \in R{1\times n} in which the element i is the% minimal cost from s to point i.% -- path \in R^{n \times n} in which the row i denotes% the shortest path from s to point i.% Copyright by MingHua Xu(徐明华), Changhzou University, 27 Jan. 2014. s=floor(s);t=floor(t);n=size(C,1);if s<1 || t < 1 || s > n || t > nerror(' The starting point and the terminal point exceeds the valid range');endif t==sdisp('The starting point and the terminal point are the same points');endlabel=ones(1,n)*inf;label(s)=0;S=[s];Sbar=[1:s-1,s+1:n];c0=0;path=zeros(n,n);path(:,1)=s;c=ones(1,n)*inf;parent=zeros(1,n);i=1; % number of points in point set S.while i<n% for each point in Sbar, replace label(Sbar(j)) by% min(label(Sbar(j)),label(S(k))+C(S(k),Sbar(j)))for j=1:n-ifor k=1:iif label(Sbar(j)) > label(S(k))+C(S(k),Sbar(j))label(Sbar(j))=label(S(k))+C(S(k),Sbar(j));parent(Sbar(j))=S(k);endendend% Find the minmal label(j), j \in Sbar.temp=label(Sbar(1));son=1;for j=2:n-iif label(Sbar(j))< temptemp=label(Sbar(j));son=j;endend% update the point set S and SbarS=[S,Sbar(son)];Sbar=[Sbar(1:son-1),Sbar(son+1:n-i)];i=i+1;% if flag==1, just output the shortest path between s and t.if flag==1 && S(i)==tson=t;temp_path=[son];if son~=swhile parent(son)~=sson=parent(son);temp_path=[temp_path,son];endtemp_path=[temp_path,s];endtemp_path=fliplr(temp_path);m=size(temp_path,2);path0(1:m)=temp_path;c_temp=0;for j=1:m-1c_temp=c_temp+C(temp_path(j),temp_path(j+1));endc0=c_temp;path(t,1:m)=path0;c(t)=c0;returnendend% Form the output resultsfor i=1:nson=i;temp_path=[son];if son~=swhile parent(son)~=sson=parent(son);temp_path=[temp_path,son];endtemp_path=[temp_path,s];endtemp_path=fliplr(temp_path);m=size(temp_path,2);path(i,1:m)=temp_path;c_temp=0;for j=1:m-1c_temp=c_temp+C(temp_path(j),temp_path(j+1));endc(i)=c_temp;c0=c(t);path0=path(t,:);endreturn。

感谢您为我指定了这个主题，让我有机会与您共享关于matlab floyd 最短路算法例题的深度和广度的文章。

在本文中，我将从浅入深地介绍这个主题，并给出相关的例题和解析，以便您能更好地理解这一算法。

1. matlab floyd最短路算法简介matlab floyd最短路算法是一种用于计算图中各顶点之间最短路径的算法。

它采用动态规划的思想，通过不断更新两点之间的最短距离来求解整个图中所有点之间的最短路径。

这个算法的时间复杂度为O(n^3)，适用于有向图或者无向图。

2. 例题分析假设我们有一个有向图，包含5个点和7条边，我们需要使用matlab floyd算法来求解任意两点之间的最短路径。

- 我们首先需要构建图的邻接矩阵，表示各点之间的距离或者权值。

我们可以根据邻接矩阵使用matlab floyd算法来求解最短路径。

- 以图中任意两点之间的最短路径为例，假设我们需要求解点1到点4之间的最短路径。

我们可以在求解过程中使用动态规划的方法，通过不断更新点1到点4的最短距离来求解最终的最短路径。

3. 个人观点和理解对于matlab floyd最短路算法，我个人认为它是一种非常实用且高效的算法。

尤其是对于大规模的图，使用matlab floyd算法可以快速地求解各点之间的最短路径，为很多实际问题的求解提供了便利。

总结与回顾通过本文的介绍和例题分析，相信您对matlab floyd最短路算法已有了更深入的理解。

希望本文能够对您有所帮助，也欢迎您共享更多关于这个主题的想法和见解。

以上是本文对matlab floyd最短路算法的介绍和分析，希望能够带给您一些启发和帮助。

如果还有其他疑问或者需要进一步讨论，欢迎随时与我交流。

matlab floyd最短路算法是一种非常重要的图论算法，它能够在有向图或者无向图中高效地求解任意两点之间的最短路径。

在本文中，我们将更加深入地了解matlab floyd最短路算法的原理和实际应用，并通过详细的例题分析来加深对该算法的理解。

用matlab寻找赋权图中的最短路中的应用1引言图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。

这些古老的难题，吸引了很多学者的注意。

1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。

在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。

最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。

2 最短路2.1 最短路的定义（short-path problem）对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能ij够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。

后来海斯在Dijkstra算法的基础之上提出了海斯算法。

但这两种算法都不能解决含有负权的图的最短路问题。

因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。

但在现实生w≥的情况下选择Dijkstra算法。

活中,我们所遇到的问题大都不含负权,所以我们在()0ij若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。

定义1：若图G=G（V，E）中个边[v i,v j]都赋有一个实数w ij ，则称这样的图G为赋权图，w ij 称为边[v i,v j]上的权。

安庆师范学院学报（自然科学版）２００７年１问题的提出设Ｇ＝（Ｖ，Ｅ）为连通图，顶点集为｛１，２，３，…ｎ｝，图中各边（ｉ，ｊ）有非负权ｃｉｊ（当（ｉ，ｊ）不是边时，权等于ｉｎｆ；当（ｉ，ｊ）是有向边时，ｃｊｉ与ｃｉｊ可以不相等），求一条道路使它是从顶点１到顶点ｎ的所有道路中总权数最小的路，这就是图论中的最短路问题［１］。

解决这个问题至今公认最好的方法是１９５９年提出Ｄｉ－ｊｋｓｔｒａ算法，它用于计算一个点ｓ到其他所有点的最短路。

此算法基本原理是：若某条路是最短路，这条路上的任意一段路也是连接这段路两个端点的最短路［１，２］。

２算法描述［３，４］第一步将点ｓ标上永久性标记Ｐ（ｓ）＝０，表示从开始点ｓ到达点ｓ的最短距离是零。

第二步将其余的顶点标上Ｔ标记，Ｔ记号是试探性标记，点ｊ的Ｔ标记Ｔ（ｊ）分两部分，Ｔ（ｊ）＝Ｔ１（ｊ）（Ｔ２（ｊ）），第一部分Ｔ１（ｊ）为从开始点ｓ经过带Ｐ标记的点到达ｊ点的最短路的权和，括号中Ｔ２（ｊ）为第二部分，是这最短路中ｊ点的前一点（如有多条最短路，则Ｔ２（ｊ）可能有多值）。

不能经过带Ｐ标记的点到达的点的Ｔ１值是无穷大（用ｉｎｆ表示），Ｔ２是空集。

第三步若这些带有Ｔ标记中权和数Ｔ１最小的点是ｋ，则点ｋ是带Ｐ标记的点外与开始点ｓ最近的点。

把点ｋ的Ｔ标记改为Ｐ标记，如果权和数最小的点有多个，则把它们都改为Ｐ标记。

若点ｎ不是Ｐ标记，转第二步（对带有Ｔ标记的点重新标记，直至点ｎ为Ｐ标记为止）。

第四步追寻最短路，从终点ｎ开始逆向逐次求最短路经过的点权和为Ｐ（ｎ）．从算法直接可见所得到的路是最短路。

上述算法更具体的步骤如下：不妨设开始点的标号是１。

⑴设Ｎ＝０，Ｐ（１）＝０，其余各点都是Ｔ标记，Ｔ１值为无穷大，Ｔ２值为空集。

⑵若ｖｉ点为刚成为Ｐ标记的（一个或几个）点，将所有与这些ｖｉ相邻的带有Ｔ标记的点ｖｊ的Ｔ标记的值改为；若Ｔ１（ｖｊ，Ｎ＋１）＝Ｐ（ｖｉ）＋ｃｉｊ，则Ｔ２（ｖｊ，Ｎ＋１）＝ｖｉ，若Ｔ１（ｖｊ，Ｎ＋１）＝Ｔ１（ｖｊ，Ｎ），则Ｔ２（ｖｊ，Ｎ＋１）＝Ｔ２（ｖｊ，Ｎ），（因此Ｔ２可能是多值的）。

图论算法及其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=[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 %程序结束图6-4Kruskal避圈法：将图G中的边按权数从小到大逐条考察, 按不构成圈的原则加入到T 中(若有选择时, 不同的选择可能会导致最后生成树的权数不同), 直到q (T ) = p (G ) − 1为止, 即T的边数= G的顶点数− 1为止.Kruskal避圈法的MATLAB程序代码如下：n=8;A=[0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0];k=1; %记录A中不同正数的个数for(i=1:n-1)for(j=i+1:n) %此循环是查找A中所有不同的正数if(A(i,j)>0)x(k)=A(i,j); %数组x记录A中不同的正数kk=1; %临时变量for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end%排除相同的正数k=k+kk;end;end;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x中不同的正数从小到大排序if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T中所有的元素赋值为0q=0; %记录加入到树T中的边数for(s=1:k)if(q==n)break;end%获得最小生成树T, 算法终止for(i=1:n-1)for(j=i+1:n)if (A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T中TT=T; %临时记录Twhile(1)pd=1;%砍掉TT中所有的树枝for(y=1:n)kk=0;for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end%寻找TT中的树枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end%砍掉TT中的树枝if(pd)break;end;end%已砍掉了TT中所有的树枝pd=0;%判断TT中是否有圈for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;endif(pd)T(i,j)=0;T(j,i)=0;%假如TT中有圈else q=q+1;end;end;end;end;endT %显示近似最小生成树T, 程序结束求二部图G的最大匹配的算法(匈牙利算法), 其基本思想是：从G的任意匹配M开始, 对X中所有M的非饱和点, 寻找M−增广路. 若不存在M−增广路, 则M为最大匹配; 若存在M−增广路P, 则将P中M与非M的边互换得到比M多一边的匹配M1 , 再对M1重复上述过程.设G = ( X, Y, E )为二部图, 其中X = {x1, x2, … , x n }, Y = { y1, y2, … , y n}. 任取G的一初始匹配M (如任取e∈E, 则M = {e}是一个匹配).①令S = φ , T = φ , 转向②.②若M饱和X \S的所有点, 则M是二部图G的最大匹配. 否则, 任取M的非饱和点u∈X \ S , 令S = S ∪{ u }, 转向③.③记N (S ) = {v | u∈S, uv∈E}. 若N (S ) = T, 转向②. 否则取y∈N (S ) \T. 若y是M 的饱和点, 转向④, 否则转向⑤.④设x y∈M, 则令S = S ∪{ x }, T = T ∪{ y }, 转向③.⑤u −y路是M−增广路, 设为P, 并令M = M⊕P, 转向①. 这里M⊕P = M∪P \M∩P, 是对称差.由于计算M−增广路P比较麻烦, 因此将迭代步骤改为：①将X中M的所有非饱和点(不是M中某条边的端点)都给以标号0和标记*, 转向②.②若X中所有有标号的点都已去掉了标记*, 则M是G的最大匹配. 否则任取X中一个既有标号又有标记*的点x i , 去掉x i的标记*, 转向③.③找出在G中所有与x i邻接的点y j (即x i y j∈E ), 若所有这样的y j都已有标号, 则转向②, 否则转向④.④对与x i邻接且尚未给标号的y j都给定标号i. 若所有的y j都是M的饱和点, 则转向⑤, 否则逆向返回. 即由其中M的任一个非饱和点y j的标号i找到x i, 再由x i的标号k找到y k , … , 最后由y t的标号s找到标号为0的x s时结束, 获得M−增广路x s y t…x i y j, 记P = {x s y t, …, x i y j }, 重新记M为M⊕P, 转向①.⑤将y j在M中与之邻接的点x k (即x k y j∈M), 给以标号j和标记*, 转向②.例1求图6-9中所示的二部图G的最大匹配.图6-9匈牙利算法的MATLAB程序代码如下：m=5;n=5;A=[0 1 1 0 01 1 0 1 10 1 1 0 00 1 1 0 00 0 0 1 1];M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end%求初始匹配Mif(M(i,j))break;end;end%获得仅含一条边的初始匹配Mwhile(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;endif(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中一个既有标号又有标记*的点xiif(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都给以标号iif(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;endif(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-增广路Pk=k+1;endfor(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;endif(pd)break;end;end%假如X中所有有标号的点都已去掉了标记*, 算法终止M %显示最大匹配M, 程序结束利用可行点标记求最佳匹配的算法步骤如下：设G = ( X , Y , E , F )为完备的二部赋权图, L 是其一个初始可行点标记, 通常取.,,0)(},|)(max{)(Y y X x y L Y y xy F x L ∈∈ =∈= M 是G L 的一个匹配. ① 若X 的每个点都是M 的饱和点, 则M 是最佳匹配. 否则取M 的非饱和点u ∈X , 令S = {u }, T = φ , 转向②.② 记N L (S ) = {v | u ∈S , uv ∈E L }. 若N L ( S ) = T , 则G L 没有完美匹配, 转向③. 否则转向④.③ 调整可行点标记, 计算a L = min { L ( x ) + L ( y ) − F (x y ) | x ∈S , y ∈Y \T }.由此得新的可行顶点标记H (v ) =,,),(,)(,)(T v S v v L a v L a v L L L ∈∈+−令L = H , G L = G H , 重新给出G L 的一个匹配M , 转向①.④ 取y ∈N L ( S ) \T , 若y 是M 的饱和点, 转向⑤. 否则, 转向⑥.⑤ 设x y ∈M , 则令S = S ∪{ x }, T = T ∪{ y }, 转向②.⑥ 在G L 中的u − y 路是M −增广路, 记为P , 并令 M = M ⊕P , 转向①.利用可行点标记求最佳匹配算法的MATLAB 程序代码如下：n=4;A=[4 5 5 12 2 4 64 2 3 35 0 2 1];for (i=1:n)L(i,1)=0;L(i,2)=0;endfor (i=1:n)for (j=1:n)if (L(i,1)<A(i,j))L(i,1)=A(i,j);end ; %初始可行点标记LM(i,j)=0;end ;endfor (i=1:n)for (j=1:n) %生成子图Glif (L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;else Gl(i,j)=0;end ;end ;endii=0;jj=0;for (i=1:n)for (j=1:n)if (Gl(i,j))ii=i;jj=j;break ;end ;endif (ii)break ;end ;end %获得仅含Gl 的一条边的初始匹配MM(ii,jj)=1;for (i=1:n)S(i)=0;T(i)=0;NlS(i)=0;endwhile (1)for (i=1:n)k=1;否则.for(j=1:n)if(M(i,j))k=0;break;end;endif(k)break;end;endif(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;endif(jsn==jst)pd=1; %判断NL(S)=T?for(j=1:jsn)if(NlS(j)~=T(j))pd=0;break;end;end;endif(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;endif(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) %生成子图GLif(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;else Gl(i,j)=0;endM(i,j)=0;k=0;end;endii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;endif(ii)break;end;end%获得仅含Gl的一条边的初始匹配MM(ii,jj)=1;breakelse%NL(S)≠Tfor(j=1:jsn)pd=1;%取y∈NL(S)\Tfor(k=1:jst)if(T(k)==NlS(j))pd=0;break;end;endif(pd)jj=j;break;end;endpd=0;%判断y是否为M的饱和点for(i=1:n)if(M(i,NlS(jj)))pd=1;ii=i;break;end;endif(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj); %S=S∪{x}, T=T∪{y}else%获得Gl的一条M-增广路, 调整匹配Mfor(k=1:jst)M(S(k),T(k))=1;M(S(k+1),T(k))=0;endif(jst==0)k=0;endM(S(k+1),NlS(jj))=1;break;end;end;end;endMaxZjpp=0;for(i=1:n)for(j=1:n)if(M(i,j))MaxZjpp=MaxZjpp+A(i,j);end;end;endM %显示最佳匹配MMaxZjpp %显示最佳匹配M的权, 程序结束从一个可行流f 开始, 求最大流的Ford--Fulkerson 标号算法的基本步骤：⑴ 标号过程① 给发点v s 以标号(+, +∞) , δ s = +∞.② 选择一个已标号的点x , 对于x 的所有未给标号的邻接点y , 按下列规则处理：当yx ∈E , 且f yx ＞0时, 令δ y = min { f yx , δ x }, 并给y 以标号 ( x − , δ y ).当xy ∈E , 且f xy ＜C xy 时, 令δ y = min {C xy − f xy , δ x }, 并给y 以标号 ( x + , δ y ). ③ 重复②直到收点v t 被标号或不再有点可标号时为止. 若v t 得到标号, 说明存在一条可增广链, 转⑵调整过程; 若v t 未得到标号, 标号过程已无法进行时, 说明f 已经是最大流.⑵ 调整过程④ 决定调整量δ =δ vt , 令u = v t .⑤ 若u 点标号为( v +, δ u ), 则以f vu + δ 代替f vu ; 若u 点标号为( v −, δ u ), 则以 f vu − δ 代替f vu .⑥ 若v = v s , 则去掉所有标号转⑴重新标号; 否则令u = v , 转⑤.算法终止后, 令已有标号的点集为S , 则割集(S , S c )为最小割, 从而W f = C (S , S c ). 例1 求图6-19所示网络的最大流.利用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 记录标号图6-19while(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)<C(i,j)) %对于未给标号的点vj, 当vivj为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(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(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; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end%计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束设网络G = ( V , E , C ), 取初始可行流 f 为零流, 求解最小费用流问题的迭代步骤： ① 构造有向赋权图 G f = ( V , E f , F ), 对于任意的v i v j ∈E , E f , F 的定义如下：当f ij = 0时, v i v j ∈E f , F ( v i v j ) = b ij ;当f ij = C ij 时, v j v i ∈E f , F ( v j v i ) = −b ij ;当0＜ f ij ＜C ij 时, v i v j ∈E f , F ( v i v j ) = b ij , v j v i ∈E f , F ( v j v i ) = −b ij .转向②.② 求出有向赋权图G f = (V , E f , F )中发点v s 到收点v t 的最短路µ , 若最短路µ存在转向③; 否则f 是所求的最小费用最大流, 停止.③ 增流. 同求最大流的方法一样, 重述如下：令.,,,−+∈∈ −=µµδj i j i ij ij ij ij v v v v f f C δ = min {δ ij | v i v j ∈µ}, 重新定义流f = { f ij }为 f ij =,,,,−+∈∈ −+µµδδj i j i ijij ij v v v v f f f如果W f 大于或等于预定的流量值, 则适当减少δ 值, 使W f 等于预定的流量值, 那么 f 是所求的最小费用流, 停止; 否则转向①.求解含有负权的有向赋权图G = ( V , E , F )中某一点到其它各点最短路的Ford 算法. 当v i v j ∈E 时记w ij = F (v i v j ), 否则取w ii =0, w ij = +∞(i ≠j ). v 1到v i 的最短路长记为π ( i ), v 1到v i 的最短路中v i 的前一个点记为θ ( i ). Ford 算法的迭代步骤：① 赋初值π (1) = 0, π ( i ) = +∞, θ ( i ) = i , i = 2, 3, … , n .② 更新π ( i ), θ ( i ). 对于i = 2, 3, … , n 和j = 1, 2, … , n , 如果π ( i )＜π ( j ) + w ji , 则令π ( i ) = π ( j ) , θ ( i ) = j .　③　终止判断：若所有的π ( i )都无变化, 停止; 否则转向②.　在算法的每一步中, π ( i )都是从v 1到v i 的最短路长度的上界. 若不存在负长回路, 则从v 1到v i 的最短路长度是π ( i )的下界, 经过n −1次迭代后π ( i )将保持不变. 若在第n 次迭代后π ( i )仍在变化时, 说明存在负长回路.其它.例2 在图6-22所示运输网络上, 求s 到t 的最小费用最大流, 括号内为(C ij , b ij ).求最小费用最大流算法的MATLAB 程序代码如下：n=5;C=[0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0]; %弧容量b=[0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 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 ;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 的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=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 %后向弧调整量if (dvt>dvtt)dvt=dvtt;endif (s(t)==1)break ;end %当t 的标号为vs 时, 终止计算调整量t=s(t);end %继续调整前一段弧上的流fpd=0;if (wf+dvt>=wf0)dvt=wf0-wf;pd=1;end %如果最大流量大于或等于预定的流量值t=n;while (1) %调整过程if (a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整elseif (a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整if (s(t)==1)break ;end %当t 的标号为vs 时, 终止调整过程t=s(t);endif (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 %计算最小费用f %显示最小费用最大流图6-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束。