图论中最短路问题及其应用

　　虽然图论这一术语直到1878年才被明确提出，但图论的思想很早就出现于对一些古代数学游戏中有趣问题的研究，比如流传于民间的许多游戏难题：迷宫问题、棋盘问题、马行走路线问题。一些著名的图论问题，如德国物理学家Kochhoff和英国数学家Kelley在各自研究领域中提出的树的概念，用图的方法成功地解决了Konigsberg七桥的问题；哈密尔顿的周游世界问题(1856);四色问题(1852年)等等。

　　图论的先驱被公认为是18世纪瑞士伟大的数学家欧拉，他在1736年发表的“第七桥问题”一文中解决了这个问题。本文被公认为图论史上的第一篇论文，因此欧拉被誉为图论之父。哥德堡由日耳曼骑士团于1308年建立，400年来一直是日耳曼军队的前沿阵地，曾经是东普鲁士的首都。二战后更名为加里宁格勒,成为前苏联的海军基地,现位于立陶宛与波兰之间,属俄罗斯。

　　二战期间德国入侵波兰后，苏联入侵德国，使其成为历史上的城市。这里便成了许多为人出生和成长的地方，其中有两个最为出名，其一便是一位蜚声18世纪的著名理想主义哲学家康德，他一生从未离开过这座城市；另一位是希尔伯特，一位19世纪的数学家。

　　科尼斯堡坐落于前苏联的加里宁格勒，自古以来便始终是普鲁士东部省德国的首府。普雷格尔河穿过城堡，有两个小岛A和D，以及连接岛屿和河岸以及岛屿和岛屿的七座桥梁。随着古老的哥德堡大学在岛上，教堂，康德的墓地和雕像，城市的居民，特别是大学生，经常沿着河桥走。问题是：从这四块土地中的每一处出发，每座桥只能经过一次，然后才能回到起点一次。这是著名的哥德堡七桥问题。哥德堡七号大桥的问题似乎并不复杂，因此它立即引起了许多人的注意，他们中的许多人正在尝试各种步行方法，但没有一个人这样做过。要得到一个清晰、理想的答案似乎并不容易。为了解决七桥问题，欧拉将问题转化为数学问题.他认为，这种方法的存在与两侧和两岛的大小和形状以及桥梁的长度和长度无关。重要的是，有几座桥梁连接这两个陆地区块。所以他用一个点来表示土地面积，用一段线连接相应的顶点来表示桥梁。问题是：在这个图中，从任何一点开始，经过每条边界一次，最后回到那个点，这样的路径是否存在？结果，问题变得更加简单和清晰，同时也变得更加普遍和深刻。这样，七桥问题就变成了绘画问题。

　　起初，人们想要找到一条没有重复的道路，而欧拉认为有那么多人失败了，也许根本就没有这样的路线。所以欧拉一直在考虑是否有一条不重复的路线。欧拉在对画的结构特征进行充分考虑之后发现，每一个笔画所绘制的图形实际上都有某一个共同的特点，即每一条线在经过某一点的中间的时候，便需要从这一点出发画出一条线，如果起点与终点重合,那么,连这个点也应该与偶数条相连。在哥德堡七桥问题的几何图形中，三点B、C、D与三条线相连，A点与五条线相连。这些联系都很奇怪。因此，欧拉的介绍：不可能在笔画这个数字。换句话说，七座桥之间没有重复的路线。欧拉对七座桥的研究是最早对拓扑学进行的探究，随着计算机以及经典图论的不断发展，各种算法充分展现，特色分明[[[]DEON,PANGCY.Shortest Path Algorithms:Taxonomy and Annotation[J].Networks,1984,14:275-323.

　　最短路径问题作为图论中最经典的问题，我们对于最短路径问题的研究不仅对图论有理论研究价值，而且对于也很有实际价值。最短路径问题在实际生活中有着广泛的应用，如GPS导航、管道铺设、基于位置的服务GPS)和交通网络优化设计等。从20世纪50年代末，人们便开始对最短路径问题进行研究。到目前为止，已有2000多篇关于这一问题的文章。它们大多在和图的整体组合先关的一些议论文或者期刊之中，应用的领域较为广泛，最常见的是交通领域。最短路径问题的计算机求解一直是交通分析和规划中不可缺少的环节。这也越来越广泛地应用于大规模的数学模型.寻找一种高效、快速的最短路径算法显得越来越重要。目前，在交通问题和计算机网络通信问题中广泛应用的最短路径问题主要是Dijkstra算法，它在图中找到给定顶点与其他顶点之间的最短路径。Floyd Floyd(1962)和Dantaig(1967)提出了求图中任意一对顶点的最短算法。该扫描方法能够计算图中任意一个点到其余点之间的任意第K个最短路径。将其推广得到的福劳德算法和但茨希算法[[[]陈启美，金陵，王从侠.高速公路通信收费监控系统构成与进展[M].北京：国防工业出版社，2006：358-363.

　　]]，以上两种方法可以计算图中的任意两个点的第K个最短路径的大小值。另外一种常见的算法叫做A*算法[[[]柴登峰，张登荣.前N条最短路径问题的算法及应用[J].杭州：浙江大学学报（工学版）,2002，36(5)531-534.]][[[]MOUSKOS K C,GREENFIELD J.A GIS Based Multimodal Advanced TravelInformation System[J].Computer Aided Civil and Infrastructure Engineering,1999，14(4):267-279.]][[[]EPPSTEIN D.Finding the K-Shortest Paths[J].SIAM Journal on Computing,1999,28(2):652-673.]][[[]JOHN H,MATTHEW M,SUBHASH S.Finding the K-shortest Simple Paths:]]，它的的应用场合一般是在计算机网络中，该场景的网络数量极大，其中的定点数量常常为指数级别的，在现实的一般应用中不是十分的常见。

　　本文主要介绍Dijkstra和Floyed这两种算法的基本定义及算法，并且通过引入商人过河这个经典问题，来阐释图论中最短路问题。除此之外，附上代码部分来说明最短路问题在实际中的应用。

　　图的2.1定义如下：将这个图中的点做一个集合为V，称为点集，其中任意两个点连接成的边设为E，V和E组成的一个二元组叫做G，表示为G=（V，E），其中，顶点v是点集V中的一个元素，边称为边集E中的一个任意元素。当V和E均为可数时，图G就是一个有限的图，反之，就是一个无限的图。本文所说的图是一个有限的图。

　　图的定义2.2如下;图中边的个数来表示，图中的点的数量用表示。则当任意一个边表示为E时，如果这个边是没有顺序的，则，E就叫做无向边，E所处的图G就叫做无向图。反之，如果边E是有顺序的，也就是说是起始点，为边的终点，则该边叫做有向弧，E所处的图G就叫做有向图。

　　定义2.3两个点u，v属于V，如果边(u，v)属于E，此时，点是两个相邻的顶点，叫做边E的两个端点。当两条边和都在集合E内，并且这两个边有一个端点相同的点u，则和是相邻的两条边，就成为边和为点的关联边。

　　定义2.4如果一个边的两个端点是相同的，则该边称为一个环，如果两个点之间有多个边，则称为多个边。我们把图中既没有环有没有多边时的图叫做简单图，否则，就叫做多重图。

　　定义2.5在一般图中，与顶点x相关的边数称为顶点的度或阶，表示为deg(x)，如果a是环，则a将x的度增加2。

　　定义2.6在无向图G中，如果有从顶点i到顶点j的连接路径(当然，也必须有一条从j到i的路)，那i和j是连通的。如果G是有向图，那么连接i和j的路径中的所有边都必须在同一方向上。如果一个图中的任何两个点是连通的，那么一个图就称为连通图。如果该图是有向图，则称为强连通图(请注意，这两个方向都是必需的)。

　　定义2.7在一般的连通图中，我们用就表示这两个点之间的最小的路径长度，我们叫做的距离，当见到有一种表示为时，就是指顶点x，这时的长度为0。

　　定义2.8在有向图中，对于点x存在两种度数，所有从点x出发的弧的个数叫做x的出度个数，所有以x结束的弧的个数叫做x的入度的个数。

　　定义2.9一般来说，在有向图中，所有的出度的总和等于所有的入度的总数，该值还等于图中所有的弧的总和。

　　要想用计算机语言把图识别出来，用矩阵或者表格去记录图是一个简单的方法，而且用图形的方式方法是表示一个图最直接的手段。

　　1.邻接矩阵的介绍

　　对于一个任意的图G，当时，点集，边集，A表示n阶方阵，用来表示，此时A就表示有向图G的邻接矩阵，就是以点为初始，以为结束的边的总数量。

　　2.关联矩阵

　　当图是一个非空的而且是不含环的时。有如下定义

　　这样得到的|V||E|矩阵是图的G的相互关联的矩阵。该矩阵全面的表示出了G中顶点V和边E之间的关联关系。关联矩阵的特点如下几条：

　　①矩阵的任意一列都含有两个非0的元素，也就是1;

　　②矩阵的任意一行的所有元素的总和等于相应的点的出度和入度的和；

　　③将此矩阵中的任意两行或者任意两列相互换位置之后，与行或者列对应的点和边以及编号也相互换位置。

　　对于图中如果没有相互重复的边，则，点集，我们把阶的矩阵P，其中叫做图D的可大矩阵，如下：

　　最短路径问题是图论的主要研究方向之一。它在现实生活中也有很多应用，如社交网络、物流规划、路径规划、GPS导航等。求解最短路径问题的方法很多，其中最典型的有Floyd算法、Dijkstra算法和Ford算法。与Floyd算法相比，Dijkstra算法只能找到两个指定节点之间的最短距离，只能找到指定起点的最短路径。然而，Floyd算法的计算过程相当繁琐。距离最小的问题是在网络理论中是最常见的，也是应用最多的，比如是在实际生产中的物流流程中最常见的，最常用的计算方法如下：假设图为一个连通的图，图中的边表示为，有权，其中用表示两个顶点之间没有边，若，为图G的任意两个点，我们求就是两个顶点之间所有路径的总权的最小值的路径。

　　2.4.1 Dijkstra算法主要思想

　　Dijkstra算法作为求解最短路问题的三个主流算法之一，其在多门学科中都有所涉及。其主要目的在于，从一固定节点出发到其余各点的最短路径，它是按照路径长度递增的顺序产生最短路径的算法。

　　该算法的基本思路是将任意一个顶点作为全图唯一一个开始节点，当生成的路径值最小时的树[[[]PALLOTTINOS.Shortest Path Methods:Complexity,Interrelation and New Propositions[J].Networks,1984,14:257-267.]]。根节点到该生成树的中任意一个点的路径就是该任意一点的最小值的路径，由于此算法的传统方法计算得到的权值都是非负数的，所以生成这个生成树的方法就是从这个任意点开始，从距离此点最近的点开始逐个加入到生成树中，加入时距该根节点越来越远的加入。

　　2.4.2 Dijkstra算法主要表达形式

　　Dijkstra算法一般有两种表达形式，一种是利用永久和临时标号方式，传统的

　　Dijkstra算法已经成为标号设定(Labeling Setting，简称LS)算法的代名词[[[]BERT SEKASDP.A Simple and Fast Label Correcting Algorithm for Shortest Paths[J].Networks,1993,23:703-709.]]。不断的增加的方式产生具有长期有效的标志符号，或者用另外一种表表示：OPEN或者CLOSE。

　　一、标号方式算法步骤

　　S:是拥有长期有效的点的集合

　　:是该算法中固定不变的起始点

　　：是顶点v的表示符号，也就是表示起点到点的距离的最小值；

　　：是表示该树的父亲节点，是确定最短路径的链条；

　　：该算法中目前所处的节点；

　　输入:在加权的图中带权的邻接矩阵

　　图1.用标号表示Dijkstra算法的步骤

　　如果，用邻接矩阵arcs且带权的表达带权的有向图时，权值就表示弧的值，则在

　　C程序语言表达的Dijkstra为如下：

　　二、Dijkstra算法OPEN-CLOSE表算法步骤

　　首先建立OPEN和CLOSE两个表。前者是将没有算过的节点的集合，后者是已经被计算过的节点。

　　1)访问网络中最近且未被访问的点，将其放OPEN组中，等待检查。

　　2)查找从OPEN表到起点的最近点，查找该点的所有子节点，并将该点放置在CLOSE表中。

　　3)逐个查找此点的全部节点。计算出这些节点与该节点之间的长度值，把该节点存入OPEN里面去。

　　4)循环2)和3)两个步骤，知道OPEN表里面没有节点或者没有了目标点。

　　2.4.3 Dijkstra算法性能分析

　　在该算法中，没有顺序的节点的存放个主要在无序表中，当查找与目前节点的相邻的节点的时候，应该计算其余剩下的全部的点，这个过程是该算法的弱点。从上面的程序中我们可见，第二步和第三步是算法的核心步骤，每次计算出当前节点的最小权值时，需要将所有的V集合和S集合的差集上进行查找，但是所有的节点都是没有任何规律的存放在链表或者是数组上面，这样程序运行时就需要耗费很长的时间；而且，查找权值的最小值这个过程，有些节点会被查询很多次，也就是需要花费更多的时间和运算。

　　2.4.4 Dijkstra算法的改进

　　在经典的Dijkstra算法中，节点以无序的方式存储在无序表中。每次搜索到当前检查点附近的节点时，需要经过所有节点并成为算法的重点。从Dijkstra标记算法描述过程中可以看出，第二步和第三步是算法效率的关键。由于每个节点搜索最小权重（vj）需要扫描V-S集上的所有节点，并且这些节点被存储在链表或阵列中乱序，这需要大量的时间；此外，搜索是最小的。在权重的过程中，会出现一些节点被多次访问的情况，增加额外的计算负载。为了解决这一问题，最有效的方法是根据边缘的权值来排列待扫描的点，使得每个周期可以用来获得满足条件的点，这可以极大地提高算法的效率。这也是基于传统Dijkstra算法的各种优化算法的重要出发点之一。另一种优化方法是在路由分析过程中减少搜索节点的数量，以便尽快到达目标点。由于这些算法主要诞生于计算机科学和运筹学领域，在算法设计过程中只考虑抽象网络的拓扑特征，算法的时间复杂度通过各种NE得到理论上的降低。w计算机数据结构和运筹学方法。度，而忽略特定网络可能具有的空间分布特性。这正是描述传输网络结构的稀疏映射和描述拓扑的其他方案之间的根本区别。

　　2.5.1 Floyd算法的基本思想

　　F1oyd算法的基本思想是:假设求从节点到的最短路径。如果从到有弧，则从到存在一条长度为的路径，此路程有可能不是最小的路程，需要计算n次以后才能确认。第一步骤是查看存在与否，若是，则在和的长度中，选择比较小的一个值。当路径上加入了一个新的节点，或者说，当和分别是目前所有节点中小于等于去的最小的路程长度，那么才可能作为节点到节点的之间的所有节点的值小于等于2的最小的路径。将该节点与上面步骤得到的节点到节点中间的路径值相比较，从剩余的节点中挑出值小于等于2的最小路径后，再接着增加一个，循环进行计算。直至，通过n次计算后，求得从到的最短路径[[[]石为人，王楷.基于Floyd算法的移动机器人最短路径规划研究[D].重庆：重庆大学自动化学院，2009

　　首先，本课题在选题及研究过程中得到穆老师的亲切关怀和悉心指导下完成的。他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。从课题的选择到项目的最终完成，穆老师都始终给予我细心的指导和不懈的支持。穆老师不仅在学业上给我以精心指导，同时还在思想、生活上给我以无微不至的关怀，在此谨向穆老师致以诚挚的谢意和崇高的敬意。

　　其次，我感谢理学院和计算机学院的诸位师长，他们的不倦指导为我打开了专业知识的宝库，让我的学术水平得到进一步的提高。

　　最后，我要感谢同窗四年的同学好友，四年来我们一起学习、互相帮助、互相进步，互相支持。四年来的每一个时刻，都是他们的陪伴和守护。我的同窗好友既是我的益友更是我的良师，在此，我要感谢他们在这四年来在学习上给予我的每一份关心和帮助，感谢他们在这四年的时间里的陪伴。感谢细心审阅我论文的各位评阅老师和答辩委员，你们的每个问题都是鼓励我在未来的科研中继续努力的动力，感谢你们的批评和指正。

　　（1）采用了较为成熟的数学理论建立模型，可行度比较高；

　　（2）在讨论商人安全渡河的方案时，运用了图表，比较直观；

　　（3）模型的求解运用了强大的matlab软件，结果可信度高，便于推广；

　　（4）通过matlab程序，能判断出“当任意个商人﹑任意个随从﹑船的容量任意时，商人能否安全渡河？”及解决了“如果能，那么渡河方案又是什么？”的问题，使得所建模型更加全面。

　　模型的缺点

　　（1）利用平面坐标法求解该模型时，出现了明显的遗漏，考虑的不够全面；

　　（2）没有找到商人数﹑随从数及船的容量之间的数量关系；

　　（3）没有考虑到实际生活中，在安全渡河的前提下，商人过河的优先级应高于随从。

　　本章主要介绍最短路应用中的经典问题商人过河问题，分别从问题的提出，问题的分析，模型的假设及其数学模型的建立这几方面对商人过河问题进行了简单介绍，并且做出了数学模型，为下一章用程序解决商人过河问题做铺垫。

　　图论作为数学界一个独特的研究方向，它自打问世就是为了解决生活中的实际问题。由图论衍生出了诸多求解算法，本文系统介绍了Dijkstra算法以及Floyd算法，从算法的基本思想出发，对算法的步骤进行介绍，以及对算法性能进行分析。

　　本文旨在借用商人过河这一经典问题，来系统的、详尽的解释图论以及最短路问题，并且通过MATLAB语言将商人过河加以实现，得出结论，商人有四种安全过河方式。