1、- 1 -用 matlab 寻找赋权图中的最短路中的应用1 引言图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。1847 年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。最短路问题是图论理论中的经典问题，寻找最
2、短路径就是在指定网络中两节点间找一条距离最小的路。2 最短路2.1 最 短 路 的 定 义 （ short-path problem）对 最 短 路 问 题 的 研 究 早 在 上 个 世 纪 60 年 代 以 前 就 卓 有 成 效 了 ， 其中对赋权图的有效算法是由荷兰著名计算机专家 E.W.Dijkstra 在 1959 年首次提出的,该算法能0ijw够解决两指定点间的最短路, 也可以求解图 G 中一特定点到其它各顶点的最短路。后来海斯在 Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由 Ford 提出了 Ford 算法,它能有效地解
3、决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权, 所以我们在 的情况下选择 Dijkstra 算法。0ijw若 网 络 中 的 每 条 边 都 有 一 个 数 值 (长 度 、 成 本 、 时 间 等 )， 则 找 出 两 节 点 (通 常 是源 节 点 和 阱 节 点 )之 间 总 权 和 最 小 的 路 径 就 是 最 短 路 问 题 。 最 短 路 问 题 是 网 络 理 论 解 决的 典 型 问 题 之 一 ， 它 不 仅 可 以 直 接 应 用 于 解 决 生 产 实 际 的 许 多 问 题 ， 如 管 路 铺 设 、线 路 安 装 、 厂 区 布 局 和 设
4、备 更 新 等 ， 而 且 经 常 被 作 为 一 个 基 本 的 工 具 ， 用 于 解 决 其 他的 做 优 化 问 题 。- 2 -定 义 1： 若 图 G=G（ V， E） 中 个 边 vi ,vj都 赋 有 一 个 实 数 wij ， 则 称 这 样 的 图 G为 赋 权 图 ， wij 称 为 边 vi ,vj上 的 权 。定 义 2： 给 定 一 个 赋 权 有 向 图 ， 即 给 一 个 有 向 图 D=（ V,A） ， 对 每 一 个 弧 a=（ vi ,vj） ， 相 应 地 有 权 w（ a） =wij， 又 给 定 D 中 的 两 个 顶 点 vs ，v t 。设 P
5、是 D 中从 vs 到 vt 的一条路，定义路 P 的权是 P 中所有弧的权之和，记为 w（P） 。最短路问题就是要在所有从 vs 到 vt 的路中，求一条权最小的路，即求一条从 vs 到 vt 的路 P0 ，使 w（P 0）= w（P）式中对 D 中所有 从 vs 到 vt 的路 P 最小，称 P0 是从 vs 到 vt 的最短路。min2.2 最短路问题算法的基本思想及其基本步骤在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra 和 Floyd 算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。在进行
6、图的遍历搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，知道获得最后的优化路径。鉴于课本使用 Dijkstra 算法，下面用 Floyd 算法进行计算：设 A=（a） n*n 为赋权图 G=（V，E ，F ）的矩阵，当 ViVj E 时，a ij =F（v i，v j） ，否则，取 aij =0，a ij =+ （i j） ，d ij 表示从 vi 到 vj 的点的距离，r ij 表示从 vi 到 vj 的点的最短路中的一个点的编号。 赋初值。对所有 i，j ，d ij = aij ，r ij =j，k=1，转向； 更新 dij ，r ij ，对所有 i，j，若 dik + dkj
7、dij ,则令 dij = dik + dkj ，r ij =k，转向； 终止判断。若 dij 0,则存在一条含有顶点 vi 的负回路，终止；或者 k=n，终止；否则，另 k=k+1，转向。最短路线可由 rij 得到。2.3 用 matlab 程序实现上述算法编写程序函数程序如下：function f=shortpath(n,A)clear;n=input(请输入矩阵的阶n=);A=input(请输入赋权图对应的n阶矩阵A=); % 顶点之间不通时，用inf表示（MATLAB中，inf表示无穷）D=A; %赋初值- 3 -for(i=1:n)for(j=1:n)R(i,j)=j;end;end
8、 %赋路径初值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; %更新rijend;end;endk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for(i=1:n) %含有负权if(D(i,j)0)pd=1;break;end;end %存在一条含有顶点的vi的负回路if(pd)- 4 -break;end %存在一条负回路，终止程序end %程序结束下面用一个实际的例子进行一下函数实际运算：例：求解下赋权图中任意两点中的最短路。V
9、1 6 V42 6 5 3 8V0 8 V2 1 V5 6 v71 7 2 4 3V3 9 V5 用 matlab 函数运行以后，运行结果如下：请输入矩阵的阶 n=8请输入赋权图对应的 n 阶矩阵 A=0 2 8 1 inf inf inf inf;2 0 6 inf 1 inf inf inf;8 6 0 7 5 1 2 inf;1 inf 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 0k =1D =0 2 8 1 Inf I
10、nf Inf Inf2 0 6 3 1 Inf Inf Inf8 6 0 7 5 1 2 Inf- 5 -1 3 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 0R =1 2 3 4 5 6 7 81 2 3 1 5 6 7 81 2 3 4 5 6 7 81 1 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8k =2D =0 2 8 1 3
11、Inf Inf Inf2 0 6 3 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 3 7 0 4 Inf 9 Inf3 1 5 4 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6- 6 -Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0R =1 2 3 4 2 6 7 81 2 3 1 5 6 7 81 2 3 4 5 6 7 81 1 3 4 2 6 7 82 2 3 2 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8k =3D =0 2 8 1 3 9 10
12、Inf2 0 6 3 1 7 8 Inf8 6 0 7 5 1 2 Inf1 3 7 0 4 8 9 Inf3 1 5 4 0 3 7 89 7 1 8 3 0 3 610 8 2 9 7 3 0 3Inf Inf Inf Inf 8 6 3 0- 7 -R =1 2 3 4 2 3 3 81 2 3 1 5 3 3 81 2 3 4 5 6 7 81 1 3 4 2 3 7 82 2 3 2 5 6 3 83 3 3 3 5 6 3 83 3 3 4 3 3 7 81 2 3 4 5 6 7 8k =4D =0 2 8 1 3 9 10 Inf2 0 6 3 1 7 8 Inf8 6 0 7
13、 5 1 2 Inf1 3 7 0 4 8 9 Inf3 1 5 4 0 3 7 89 7 1 8 3 0 3 610 8 2 9 7 3 0 3Inf Inf Inf Inf 8 6 3 0R =1 2 3 4 2 3 3 81 2 3 1 5 3 3 8- 8 -1 2 3 4 5 6 7 81 1 3 4 2 3 7 82 2 3 2 5 6 3 83 3 3 3 5 6 3 83 3 3 4 3 3 7 81 2 3 4 5 6 7 8k =5D =0 2 8 1 3 6 10 112 0 6 3 1 4 8 98 6 0 7 5 1 2 131 3 7 0 4 7 9 123 1 5
14、 4 0 3 7 86 4 1 7 3 0 3 610 8 2 9 7 3 0 311 9 13 12 8 6 3 0R =1 2 3 4 2 5 3 51 2 3 1 5 5 3 51 2 3 4 5 6 7 51 1 3 4 2 5 7 52 2 3 2 5 6 3 8- 9 -5 5 3 5 5 6 3 83 3 3 4 3 3 7 85 5 5 5 5 6 7 8k = 6D =0 2 7 1 3 6 9 112 0 5 3 1 4 7 97 5 0 7 4 1 2 71 3 7 0 4 7 9 123 1 4 4 0 3 6 86 4 1 7 3 0 3 69 7 2 9 6 3 0
15、 311 9 7 12 8 6 3 0R =1 2 6 4 2 5 6 51 2 6 1 5 5 6 56 6 3 4 6 6 7 61 1 3 4 2 5 7 52 2 6 2 5 6 6 85 5 3 5 5 6 3 86 6 3 4 6 3 7 85 5 6 5 5 6 7 8- 10 -k =7D =0 2 7 1 3 6 9 112 0 5 3 1 4 7 97 5 0 7 4 1 2 51 3 7 0 4 7 9 123 1 4 4 0 3 6 86 4 1 7 3 0 3 69 7 2 9 6 3 0 311 9 5 12 8 6 3 0R =1 2 6 4 2 5 6 51 2 6 1 5 5 6 56 6 3 4 6 6 7 71 1 3 4 2 5 7 52 2 6 2 5 6 6 85 5 3 5 5 6 3 86 6 3 4 6 3 7 85 5 7 5 5 6 7 8k = 8
