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

《图论是应用数学的一个分支》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、最短路及其matIab求解摘要本文研究的是最短路问题，而最短路问题有常用的两种算法：Dijkstra算法和Floyd算法，每个算法的思路不同，而且Floyd算法比较完备，所以本文主要针对的是Floyd算法。本文将最短路理论应用到实际生活中，当题目给定时，面对数据的难易程度，针对不同的情况，解决的思路是一致的。首先参考路线图，针对每两个节点间的路线长度，确定相应的矩阵，因为某些是无向图，有些是有向图，当没有给定两点之间的距离时，通过inf来代替；然后通过matlab软件进行程序运行，利用Floyd算法的带权邻接矩阵来解决最短路的问题；最后通过运行的结果判断结论,最后得到最短

2、路线以及距离。该算法可以求任意两节点之间的最短距离，通过矩阵来确定。但是当节点很多时，需要迭代的次数也很多，那就相当麻烦。所以为了改进传统的Floyd算法，通过插入点进行起始点到该点和该点到终点的距离进行比较，可以有效的进行忽关键i司：最短路、floyd算法、matlab软件一、问题重述在古代有这样的难题：哥尼斯堡七桥问题、棋盘上马的行走路线问题、汉米尔顿（环游世界）数学难题等等;而在实际生活中，我们也会遇到这样的问题，当需要走的路径很多时，如何寻找最优路径，因为这样不仅耗时短，还方便。这些都和图论有所关联，图论利用图作为研究对象，从而解决一些问题、难题。而最短路问题就是

3、图论理论上的一个经典问题，寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引中到其它的度量，如时间、费用、线路容量等很多方面。如图所示，某人每天从住处儿开车到工地内上班，图中各弧旁的数字表示道路的长度/公里，试问他从家出发到工地，应选择哪条路线，才能使路上行驶的总距离最短。图1.1开车上班路线⑴1.2如图所示，某人要从s城（图中节点1）到t城市（图中节点7）岀差，因无直通车，从换乘的火车在时间上能很好衔接考虑，可供选择的各城市如图中各节点所示，各城市间的火车通行方向及距离（km）均注于图屮。确定应走哪条路总长最短。二、

4、符号说明与模型假设2.1符号说明1•人表示图中的某一节点（s二1,2,...,7）2.心表示从匕到匕•的路程2.2模型假设（1）假设所有数据来源于题目已知，真实可靠。三、模型的建立与求解3.1问题一的求解3.1.1问题一的分析从图可以知道，已经给出所有路线以及相关距离，利用最短路的中的floyd算法可以求解。⑵1•最短路建立模型如下：设G二（V,E）为连通图，图中各边（％“）有权（/..=-表示片比间无边），叫*为图中任意两点，求一-条道路U,使它是从匕到岭的所有路中总权最小的路。即：厶（A）=口“最小。1212.Floyd算法：令网络的权矩阵为D=（d,）,Z,为从v,

5、.到vz的距离。V7nxnu1J其中当(%Vj)wE其它算法基本步骤:(1)输入权矩阵£>(0)=D,(2)计算D(k)=(d^)fixn(k=l,2,3,...,n)其中df=minafh)+d『】)](3)D(w)=(4rt))nxn中元素就是匕•到专的最短路长。3.1.2问题一的解答通过运行matlab程序可以得到以下结果：02891112.513.5inf067910.511.5infinf0134.55.5D-infinfinf043.56.5infinfinfinf0inf2.5infinfinfinfinf05infinfinfinfinfinfinf12

6、2222202333330034545path=0004565000050700000670000000从D矩阵可以看到从vl到v7的最短路线是vl->v2->v3->v5->v7,最短距离为13.5。2.2问题二的求解2.2.1问题二的分析和3.1.1分析的一样，利用该模型，得到运算结果。3.2.2问题二的解答通过运行matlab程序可以得到以下结果：047548590097511251400inf0200425520670945infinf0440490640915D=infinfinf0150300575infinfinfinf0150425infinfinfinf

7、inf0490infinfinfinfinfinfinf123233302345550034555path=0004555000056700000670000000从D矩阵可以看到从vl到v7的最短路线是vl-*v3-v5->v7,最短距离为1400。四、模型的评价在求解最短路的问题中，所用的是Floyd算法，但是还有Dijkstra算法，但是这种算法只是求指定两点之间的最短距离，虽然也可以求击来，但是没有Floyd算法全面，因为Floyd算法可以求任意两点之间的距离，而Dijkstra算法是求给定的一个节点到其它节点间的最短