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

最短路及其matlab求解

摘要

本文研究的是最短路问题，而最短路问题有常用的两种算法：Dijkstra算法和Floyd算法，每个算法的思路不同，而且Floyd算法比较完备，所以本文主要针对的是Floyd算法。

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

该算法可以求任意两节点之间的最短距离，通过矩阵来确定。但是当节点很多时，需要迭代的次数也很多，那就相当麻烦。所以为了改进传统的Floyd算法，通过插入点进行起始点到该点和该点到终点的距离进行比较，可以有效的进行忽略某些点，从而使算法更为直观有效。

关键词：最短路、floyd算法、matlab软件

一、问题重述

在古代有这样的难题：哥尼斯堡七桥问题、棋盘上马的行走路线问题、汉米尔顿（环游世界）数学难题等等;而在实际生活中，我们也会遇到这样的问题，当需要走的路径很多时，如何寻找最优路径，因为这样不仅耗时短，还方便。这些都和图论有所关联，图论利用图作为研究对象，从而解决一些问题、难题。而最短路问题就是图论理论上的一个经典问题，寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等很多方面。

【1】

1.1如图所示，某人每天从住处v1开车到工地v7上班，图中各弧旁的数字表示

道路的长度/公里，试问他从家出发到工地，应选择哪条路线，才能使路上行驶的总距离最短。

图1.1 开车上班路线

【1】

v2 2 6 8 v4 3.5 v6 5 v1 9 1 4 2.5 v7 v3 3 v5 1.2如图所示，某人要从s城（图中节点1）到t城市（图中节点7）出差，

因无直通车，从换乘的火车在时间上能很好衔接考虑，可供选择的各城市如图中各节点所示，各城市间的火车通行方向及距离（km)均注于图中。确定应走哪条路总长最短。

1

425 1 475 200 520 2 440 150 4 615 485 3 650 6 490 490 150 5 425 7 图1.2各城市火车通行方向及距离/km 二、符号说明与模型假设

2.1符号说明

1.vs表示图中的某一节点（s=1，2，...，7） 2.lij表示从vi到vj的路程 2.2模型假设

（1）假设所有数据来源于题目已知，真实可靠。

三、模型的建立与求解

3.1问题一的求解 3.1.1问题一的分析

从图1.1可以知道，已经给出所有路线以及相关距离，利用最短路的中的floyd算法可以求解。 【2】

1.最短路建立模型如下： 设G=（V，E）为连通图，图中各边（vi,vj）有权lij（lij=∞表示vi,vj间无边），vs,vt为图中任意两点，求一条道路μ，使它是从vs到vt的所有路中总权最小的路。即：

L????【2】

l????vi,vj?ij最小。

2.Floyd算法：

令网络的权矩阵为D=dij??n?n，lij为从vi到vj的距离。

2

?l当（vi,vj)?E其中dij??ij

其它??算法基本步骤：

（1）输入权矩阵D(0)?D，

(k)（2）计算D(k)?(dij)n?n（k=1,2,3,...,n) (k)(k?1)(k?1)(k?1)其中dij?min[dij,dik?dkj]

(n)(n)（3）D(n)?(dij就是vi到vj的最短路长。 )n?n中元素dij3.1.2 问题一的解答

通过运行matlab程序可以得到以下结果：

028609711112.513.59310.511.54.55.53.5inf0inf6.5 2.55infinf0infinfD?infinfinfinfinfinfinfinf

inf04infinf0infinfinfinfinfinf122222202333330034545path?0000000000004000550060605 770从D矩阵可以看到从v1到v7的最短路线是v1→v2→v3→v5→v7,最短距离为13.5。

3.2 问题二的求解 3.2.1问题二的分析

和3.1.1分析的一样，利用该模型，得到运算结果。 3.2.2 问题二的解答

通过运行matlab程序可以得到以下结果：

3

0infinfD?inf475485900975112514000inf2004255206700440490640inf0infinfinfinfinfinf2331500infinf33001500inf945915575 425490infinfinfinfinfinfinfinf12302345550034555path?00000000

从D矩阵可以看到从v1到v7的最短路线是v1→v3→v5→v7,最短距离为1400。

00004000550056605 770

四、模型的评价

在求解最短路的问题中，所用的是Floyd算法，但是还有Dijkstra算法，但是这种算法只是求指定两点之间的最短距离，虽然也可以求出来，但是没有Floyd算法全面，因为Floyd算法可以求任意两点之间的距离，而Dijkstra算法是求给定的一个节点到其它节点间的最短距离。总体来说，Floyd算法比较简单，而且比较快捷，当自己手算时，是非常繁琐的，但是利用计算机就可以快速地算出来。

但是在利用Floyd算法的时候，该算法需要利用带权邻接矩阵跨接v1v2...,需要迭代n次。当节点个数很大时，迭代次数也很大。vn后得到的最短距离矩阵，

在进行n次迭代时，在起始点到终点之间会存在某些插入的节点不能使路程变短，

（k)(k)可以对其简化，降低计算过程。[3]优化思路为：构造迭代矩阵D?(dij)，计算

两点vi和vj之间最短路时，对待插入的节点vr先进行路长比较，如果

(k?1)(k?1)k?1)(k?1)或d(，则说明插入节点vr后，vi经过vr到达vj的路长不dir?dij?dijrj(k?1)(k?1)会比原来的短，于是不应再考虑dir，则进入下一个节点的搜索。 ?drj五、模型的推广

4

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论是应用数学的一个分支在线全文阅读。