图论是应用数学的一个分支

最短路及其 matlab 求解 摘 要 本文研究的是最短路问题 而最短路问题有常用的两种算法 Dijkstra 算 法和 Floyd 算法 每个算法的思路不同 而且 Floyd 算法比较完备 所以本文 主要针对的是 Floyd 算法 本文将最短路理论应用到实际生活中 当题目给定时 面对数据的难易程 度 针对不同的情况 解决的思路是一致的 首先参考路线图 针对每两个节 点间的路线长度 确定相应的矩阵 因为某些是无向图 有些是有向图 当没 有给定两点之间的距离时 通过 inf 来代替 然后通过 matlab 软件进行程序运 行 利用 Floyd 算法的带权邻接矩阵来解决最短路的问题 最后通过运行的结 果判断结论 最后得到最短路线以及距离 该算法可以求任意两节点之间的最短距离 通过矩阵来确定 但是当节点 很多时 需要迭代的次数也很多 那就相当麻烦 所以为了改进传统的 Floyd 算法 通过插入点进行起始点到该点和该点到终点的距离进行比较 可以有效 的进行忽略某些点 从而使算法更为直观有效 关键词 最短路 floyd 算法 matlab 软件 1 1 问题重述 在古代有这样的难题 哥尼斯堡七桥问题 棋盘上马的行走路线问题 汉米尔顿 环游世界 数学难题等等 而在实际生活中 我们也会遇到这样的问 题 当需要走的路径很多时 如何寻找最优路径 因为这样不仅耗时短 还方 便 这些都和图论有所关联 图论利用图作为研究对象 从而解决一些问题 难题 而最短路问题就是图论理论上的一个经典问题 寻找最短路径就是在指 定网络中两结点间找一条距离最小的路 最短路不仅仅指一般地理意义上的距 离最短 还可以引申到其它的度量 如时间 费用 线路容量等很多方面 1 1 1 如图所示 某人每天从住处 开车到工地上班 图中各弧旁的数字表 1 v 7 v 示道路的长度 公里 试问他从家出发到工地 应选择哪条路线 才能使路上行 驶的总距离最短 图 1 1 开车上班路线 1 1 2 如图所示 某人要从 s 城 图中节点 1 到 t 城市 图中节点 7 出差 因无直通车 从换乘的火车在时间上能很好衔接考虑 可供选择的各城市如图 中各节点所示 各城市间的火车通行方向及距离 km 均注于图中 确定应走哪 条路总长最短 1 v 2 v 4 v 3 v 6 v 5 v 7 v 2 9 8 1 3 6 4 3 5 2 5 5 2 图 1 2 各城市火车通行方向及距离 km 二 符号说明与模型假设 2 1 符号说明 1 表示图中的某一节点 s 1 2 7 s v 2 表示从到的路程 ij l i v j v 2 2 模型假设 1 假设所有数据来源于题目已知 真实可靠 3 模型的建立与求解 3 1 问题一的求解 3 1 1 问题一的分析 从图 1 1 可以知道 已经给出所有路线以及相关距离 利用最短路的中的 floyd 算法可以求解 2 1 最短路建立模型如下 设 G V E 为连通图 图中各边 有权 表示间无边 ji vv ij l ij l ji vv 为图中任意两点 求一条道路 使它是从到的所有路中总权最小的 ts vv s v t v 路 即 最小 jiv v ij lL 2 2 Floyd 算法 令网络的权矩阵为 D 为从到的距离 nn ij d ij l i v j v 1 2 3 4 5 6 7 485 475 650 490 520440 200 425 150 490 425 615 150 3 其中 其它 当 Evvl d jiij ij 算法基本步骤 1 输入权矩阵 DD 0 2 计算 k 1 2 3 n nn k ij k dD 其中 min 1 1 1 k kj k ik k ij k ij dddd 3 中元素就是到的最短路长 nn n ij n dD n ij d i v j v 3 1 2 问题一的解答 通过运行 matlab 程序可以得到以下结果 infinfinfinfinfinfinf 50infinfinfinfinf 5 2inf0infinfinfinf 5 65 340infinfinf 5 55 4310infinf 5 11 5 109760inf 5 13 5 12119820 D 0000000 7600000 7050000 5654000 5454300 3333320 2222221 path 从 D 矩阵可以看到从 v1 到 v7 的最短路线是 v1 v2 v3 v5 v7 最短距离为 13 5 3 2 问题二的求解 3 2 1 问题二的分析 和 3 1 1 分析的一样 利用该模型 得到运算结果 3 2 2 问题二的解答 通过运行 matlab 程序可以得到以下结果 4 infinfinfinfinfinfinf 4900infinfinfinfinf 4251500infinfinfinf 5753001500infinfinf 9156404904400infinf 9456705204252000inf 140011259759004854750 D 0000000 7600000 7650000 5554000 5554300 5554320 3332321 path 从 D 矩阵可以看到从 v1 到 v7 的最短路线是 v1 v3 v5 v7 最短距离为 1400 4 模型的评价 在求解最短路的问题中 所用的是Floyd算法 但是还有Dijkstra算法 但 是这种算法只是求指定两点之间的最短距离 虽然也可以求出来 但是没有 Floyd算法全面 因为Floyd算法可以求任意两点之间的距离 而Dijkstra算法 是求给定的一个节点到其它节点间的最短距离 总体来说 Floyd算法比较简单 而且比较快捷 当自己手算时 是非常繁琐的 但是利用计算机就可以快速地 算出来 但是在利用Floyd算法的时候 该算法需要利用带权邻接矩阵跨接 1 v 2 v 后得到的最短距离矩阵 需要迭代n次 当节点个数很大时 迭代次数也很 n v 大 在进行n次迭代时 在起始点到终点之间会存在某些插入的节点不能使路程 变短 可以对其简化 降低计算过程 3 优化思路为 构造迭代矩阵 计算两点和之间最短路时 对待插入的节点先进行路长 k ij k dD i v j v r v 比较 如果或 则说明插入节点后 经过到达 1 1 d k ij k ir d 1 1 d k ij k rj d r v i v r v 的路长不会比原来的短 于是不应再考虑 则进入下一个节点的 j v 1 1 d k rj k ir d 搜索 5 模型的推广 5 在古代有这样的难题 哥尼斯堡七桥问题 棋盘上马的行走路线问题 汉 米尔顿 环游世界 数学难题等等 而在实际生活中 我们也会遇到这样的问题 当需要走的路径很多时 如何寻找最优路径 因为这样不仅耗时短 还方便 这些都和图论有所关联 图论利用图作为研究对象 从而解决一些问题 难题 而最短路问题就是图论理论上的一个经典问题 寻找最短路径就是在指定网络 中两结点间找一条距离最小的路 最短路不仅仅指一般地理意义上的距离最短 还可以引申到其它的度量 如时间 费用 线路容量等很多方面 通过操作发现可以很方便的解决此类问题 尤其是在路线安排 厂区布局 中的应用具有很重要的意义 图论与不断发展完善的计算机数据结构及算法的 有效结合使得新的最短路径算法不断的更新 从而为人们提供方便 减少计算 量 参考文献 1 朱顺泉 苏越良 管理运筹建模与求解 清华大学出版社 2011 6 192 页 194页 2 胡运权主编 运筹学教程 清华大学出版社 2011 6 242页 247页 3 张德全 吴果林等 最短路问题的Floyd加速算法与优化 2009年17期 41页 46页 6 附录 Matlab程序命令 floyd算法 function D path min1 path1 floyd a start terminal a是邻接矩阵 start是起始点 terminal是终止点 D是最小权值表 path是最短路线表 D a n size D 1 path zeros n n for i 1 n for j 1 n if D i j inf path i j j end end end for k 1 n for i 1 n for j 1 n if D i k D k j a 0 475 485 inf inf inf inf inf 0 200 425 520 inf inf inf inf 0 440 490 650 inf inf inf inf 0 150 inf 615 inf inf inf inf 0 150 425 inf inf inf inf inf 0 490 inf inf inf inf inf inf inf D path floyd a D 0 475 485 900 975 1125 1400 Inf 0 200 425 520 670 945 Inf Inf 0 440 490 640 915 Inf Inf Inf