最短路问题及其应用
顾碧芬 06200103
摘要：主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。以及这两种算法在实际问题中的应用和比较。
1 引言
最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。
最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。
2 最短路 2.1 最短路的定义
对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()
ij w ≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra 在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G 中一特定点到其它各顶点的最短路。后来海斯在Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在()
0ij w ≥的情况下选择Dijkstra 算法。
定义①
1若图G=G(V ,E)中各边e 都赋有一个实数W(e),称为边e 的权,则称这种图为赋权图,记为G=G(V,E,W)。
定义②2若图G=G(V ,E)是赋权图且()0W e ≥,()e E G ∈,若u 是i v 到j v 的路()W u 的权,则称()W u 为u 的长,长最小的i v 到j v 的路()W u 称为最短路。
若要找出从i v 到n v 的通路u ,使全长最短,即()()min ij e u
W u W e ∈=
∑。
2.2 最短路问题算法的基本思想及基本步骤
在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。
Dijkstra 算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra 算法n 次。另一种方法是由Floyd 于1962年提出的Floyd 算法,其时间复杂度为
()3O n ,虽然与重复执行Dijkstra 算法n 次的时间复杂度相同,但其形式上略为简单,且实际运
算效果要好于前者。
Dijkstra 算法基本步骤③
： 令：{}{}_
23,1,,,,i n s v i s v v v ===
并令：{
()()10,j j W v T v v s
-
==∞∈
1、 对j v s -
∈，求()(){}()
min ,j i ij j T v W v w T v +=。 2、 求
(){}min j j
v s
T v ∈得()k
T v ，使()k
T v =(){}min j j
v s
T v ∈
令()()k k W v T v =
3、若k n v v =则已找到1v 到n v 的最短路距离()k W v ，否则令i k =从s -
中删去i v 转1 这样经过有限次迭代则可以求出1v 到n v 的最短路线，可以用一个流程图来表示：
第一步 先取()10W v =意即1v 到1v 的距离为0,而()j T v 是对()
j T v 所赋的初值。 第二步 利用()1W v 已知,根据()(){}
min ,j i ij T v W v w +对()
j T v 进行修正。 第三步 对所有修正后的()
j T v 求出其最小者()k T v 。其对应的点k v 是1v 所能一步到达的点j v 中最近的一个,由于所有()0W u ≥。因此任何从其它点j v 中转而到达k v 的通路上的距离都大于1v 直接到k v 的距离()k T v ,因此()k T v 就是1v 到k v 的最短距离,所以在算法中令
()()k k W v T v =并从s 中删去k v ,若k=n 则()()k n W v W v =就是1v 到n v 的最短路线,计算结
束。否则令i k v v =回到第二步,继续运算,直到k=n 为止。
这样每一次迭代,得到1v 到一点k v 的最短距离,重复上述过程直到k n v v =。
Floyd 算法的基本原理和实现方法为:如果一个矩阵ij D d ??=??其中0ij d >表示i 与j 间的距离,若i 与j 间无路可通,则ij d 为无穷大。i 与j 间的最短距离存在经过i 与j 间的k 和不经过
k 两种情况,所以可以令1,2,3,
,k n =,n(n 为节点数)。检查ij d 与ik kj d d +的值,在此,ik d 与
kj d 分别为目前所知的i 到k 与k 到j 的最短距离,因此,ik kj d d +就是i 到j 经过k 的最短距
离。所以,若有ij ik kj d d d >+,就表示从i 出发经k 再到j 的距离要比原来的i 到j 距离短,自然把i 到j 的ij d 重写成ik kj d d +。每当一个k 搜索完,ij d 就是目前i 到j 的最短距离。重复这一过程,最后当查完所有k 时,ij d 就为i 到j 的最短距离。
3 最短路的应用 3.1在运输网络中的应用④
设6个城市126,,
,v v v 之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该
段公路的长度(单位:百公里),设你处在城市1v ,那么从1v 到6v 应选择哪一路径使你的费用最省。
解:首先设每百公里所用费用相同,求1v 到6v 的费用最少,既求1v 到6v 的最短路线。为了方便计算,先作出该网络的距离矩阵,如下:
12345
6123
4560525015921081058025910202520v v v v v v v v L v v v v ?
?
??∞∞∞????
∞??
=∞????
∞??
∞????∞∞∞??
(0)设()(){}1234560,,,,,,j W v T v v s v v v v v -
==∞∈=, (1)第一次迭代
①计算()
,2,3,4,5,6j T v j =如下
()()(){}{}22112min ,min ,055T v T v W v w =+=∞+=
()()(){}{}44114min ,min ,0T v T v W v w =+=∞+∞=∞ ()()56,T v T v =∞=∞
②取
(){}()3
2min j j
v s
T v T v ∈==,令()()33
2W v T v ==
③由于()36k n =≠=,令{}2456,,,,3s v v v v i -
==转(1) 第二次迭代:
①算()
,2,4,5,6j T v j =如下
()()(){}{}22323min ,min 5,213T v T v W v w =+=+= ()()(){}{}44334min ,min 8,288T v T v W v w =+=+= ()()(){}{}55335min ,min 10,21010T v T v W v w =+=+= ()()(){}{}66336min ,min ,2T v T v W v w =+=∞+∞=∞
②取(){}()2
min 3j j
v s
T v T v -
∈==令()()22
3W v T v ==
③由于()26k n =≠=,令{}456,,2s v v v i -
==转(1) 第三次迭代:
①算()
,4,5,6j T v j =如下
()()(){}{}44224min ,min 8,358T v T v W v w =+=+= ()()(){}{}55225min ,min 10,3910T v T v W v w =+=+= ()6T v =∞
②取(){}()()()4
4
4
min 8,8j j
v s
T v T v W v T v -
∈====
③由于()46k n =≠=,令{}56,4s v v i -
==转(1) 第四次迭代:
①算()
,5,6j T v j =如下
()()(){}{}55445min ,min 10,2810T v T v W v w =+=+=
②取(){}()()()5
5
5
min 10,10j j
v s
T v T v W v T v -
∈====
③由于()56k n =≠=,令{}6s v -
=转(1) 第五次迭代:
①算()
,6j T v j =如下
()()(){}{}66556min ,min 13,10212T v T v W v w =+=+=
②由于6k n ==。因此已找到1v 到6v 的最短距离为12。计算结束。 找最短路线:逆向追踪得132456v v v v v v →→→→→ 最短距离为12,即从城市1v 到城市6v 的距离最短,即费用最省。
3.2在舰船通道路线设计中的应用⑤
利用图论的经典理论和人群流量理论研究舰船人员通道路线的优化设计及最优线路选择。首先介绍图论相关理论,对船舶通道进行路网抽象,建立网络图,然后根据人群流动的相关理论,选取不同拥挤情况下的人员移动速度,从而确定各条路段(包括楼梯)的行程时间。以行程时间作为通道网络的路权，得出路阻矩阵以选择一对起点/终点的最短时间路线为目标,建立最短路径问题的数学模型,利用经典的Floyd 算法确定最短路径。将此方法应用于某舰艇多层甲板的通道网络中,计算结果并进行讨论,最后在此研究的基础上对通道设计相关问题的深化和拓展进行了探讨和总结,并提出设想。
路线优化技术通常采用图论中的“图”来表示路网,船舶通道路网与图论的路网对应关系为:结点———通道的交叉口或断头路的终点;边———两结点之间的路段称为边,若规定了路段的方向,则称为弧;边(弧)的权———路段某个或某些特征属性的量化表示。
路权的标定决定了最短的路径搜索依据,也就是搜索指标。根据不同的最优目标,可以选择不同的路段属性。由于舰船上除了平面上的通道之外还有垂直方向的楼梯(或直梯),如果以
最短路程距离作为优化目标,路线的效率未必最高(距离最短未必耗时最少)。所以,以最短行程时间作为优化的目标,道路权重即为各路段的平均行程时间。
对于要研究的对象,取各条通道的起点(或终点)和交叉点为图的顶点,各路段为边,路权为路段行走的平均时间。寻找从起点到终点的最短时间路径即为最优路径。在规定了结点、边和权值以后,便将路网抽象为一个赋权无向图或赋权有向图,从而确定路网中某两地间的最优路线便转化为图论中的最短路径问题。
首先将空间问题抽象为图,图2为某舰的两层甲板的部分抽象图,上下两个平面上纵横交错的直线为各层甲板的主要通道,连接两层甲板的直线表示楼梯,包括2个直梯和3个斜梯。
每条路段上的标注(),a b中,a表示路段实际长度或者楼梯的类型,m;b表示此路段的行程时间(即路权),s如(40,32)。
图2 两层甲板的部分抽象图
图3 赋权图
再利用上述求最短的方法即可求得需要的通道路线。
4 结语
本文将最短路理论应用到实际生活中，尤其是在舰船通道路线中的应用具有很重要的意
义。将实际生活中出现的安全隐患尽量降低。同时也凸显出学习和应用最短路问题原理的重
要性。另外，最短路问题在城市道路建设、物资供应站选址等问题上也有很重要的作用。分
析和研究最短路问题趋于热门化。
注：①殷剑宏,吴开亚.图论及其算法M. 中国科学技术出版社②秦裕瑗,秦明复.运筹学简明教材M. 高等教育出版社③卜月华图论及其应用④最短路问题在运输网络中的应用⑤基于图论的舰船通道路线优化
参考文献：
【1】卜月华图论及其应用南京：东南大学出版社，2000
【2】基于图论的舰船通道路线优化余为波王涛2008
【3】最短路问题在运输网络中的应用李玲2006
【4】戴文舟. 交通网络中最短路径算法的研究[D ]. 重庆大学硕士学位论文,2004. 【5】谢灼利,等.地铁车站站台火灾中人员的安全疏散[J].中国安全科学学报,2004,14(7):21.
【6】荣玮.基于道路网的最短路径算法的研究与实现.武汉理工大学硕士学位论文
[D],2005.
【7】朱建青,张国梁.数学建模方法M. 郑州大学出版社.
【8】杨民助,运筹学M. 西安交通大学出版社.
【9】殷剑宏,吴开亚.图论及其算法M. 中国科学技术出版社.
最短路算法及其应用 广东北江中学余远铭【摘要】 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。 【关键字】 最短路 【目录】 一、基本概念 (2) 1．1 定义 (2) 1．2简单变体 (2) 1．3负权边 (3) 1．4重要性质及松弛技术 (4) 二、常用算法 (5) 2．1 Dijkstra算法 (5) 2．2 Bellman-Ford算法 (7) 2．3 SPFA算法 (8) 三、应用举例 (10) 3．1 例题1——货币兑换 (10) 3．2 例题2——双调路径 (11) 3．3 例题3——Layout (13) 3．4 例题4——网络提速 (15) 四、总结 (18)
【正文】 一、基本概念 1．1 定义 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并 在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是没必要考虑的。 下面我们将阐明如何有效地解决这类问题。在最短路问题中，给出的是一 有向加权图G=(V ,E)，在其上定义的加权函数W:E →R 为从边到实型权值的映射。路径P=(v 0, v 1,……, v k )的权是指其组成边的所有权值之和： 11()(,)k i i i w p w v v -==∑ 定义u 到v 间最短路径的权为 {}{}min ():)w p u v u v v δυ→(,=∞ 如果存在由到的通路 如果不存在 从结点u 到结点v 的最短路径定义为权())w p v δυ=(,的任何路径。 在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。 边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示 时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。 1．2简单变体 单目标最短路径问题： 找出从每一结点v 到某指定结点u 的一条最短路 径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u 和v ，找出从u 到v 的一 条最短路径。如果我们解决了源结点为u 的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。 每对结点间的最短路径问题：对于每对结点u 和v ，找出从u 到v 的最短 路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。
下面的程序是蚁群算法在最短路中的应用，稍加扩展即可应用于机器人路径规划function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/ac17542082.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数）
金华双龙洞旅游路线中最短路问题 摘要： 金华双龙洞景点分布较多，通过对其旅游路线的设置，转化为图论内容中的最短路情景进行讨论，建立模型，并通过搜索资料，利用几种方法解决路线最小的问题。 关键字： 数学建模最短路问题 lingo Dijkstra法 flod算法 一、研究背景： 在旅游过程中，我们常常感觉到自己一天下来走了很多路，回到宾 馆脚痛的不行。但其实我们可以利用运筹学的知识，通过建立数学 模型，转化为图论的内容。从而较为合理的制定出选择的路线（即 最短路问题）。 因而这次的小论文，我主要探究一下几个问题： 1.从景点进口到出口的最短路程。（最短路问题） 2.从景点到出口的最长路线。 3.建立的模型是否满足能回到起点（古典图论问题） 二、研究内容： 根据从互联网中搜索的资料，金华双龙洞的主要景点：景区进口双 龙洞，冰壶洞，朝真洞，桃源洞，黄大仙祖宫五个，其余为小景点 （若要加入，同样可以按照以下问题的研究方法进行讨论）现在忽 略。 问题总假设：分别设置双龙洞，冰壶洞，朝真洞，桃源洞，黄大仙 祖宫五个景点为A,B,C,D,E五点，根据现实及假设，可以得到如图 所示的路线图：
再利用用Dijkstra算法求解无负权网络的最短路。同时也可以利用此法算出最长路程。 问题一的解决：以A为景点出口，E为出口。 故A点标号为P（a）=0 给其余所有的T标号T（i）=+∞ 考虑与A相邻的两个顶点BC，两个顶点为T标号，故修改这两个点的标号为：T(b)=min[T(b),P(a)+l12]=min[+∞,0+3]=3 T(c)=min[T(c),P(a)+l13]=min[+∞,0+2]=2 比较所有T标号，T(c)最小，所以令P(c)=2 再考察（C,B）(C,D)(C,E)的端点：同理可得 T(b)=6 T(d)=6.8 T(e)=10.2(显然已经到终点但还需要看看其余路线长短) 故又令P（b）=6.综合分析只有一条线路即A→C→B→D→E 此时总路程为2+4+3+8.4=16.4>10.2 所以，最短路程为A→C→E。即当游客不想再看双龙洞时或者因为脚伤等因素需以最小路程离开时，可以路线A→C→E离开景区。 特殊情况的处理：游客一定要去B景点则在一开始就应该先选择 B，而非C。才能使路线最短。因此，对于特殊问题，我们应当具体 问题，具体分析。
图论及其应用 学时：40 学分：2 课程属性：专业选修课开课单位：理学院 先修课程：高等代数后续课程：无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配，求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配，求最大匹配算法及应用 6
7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材： [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩．图论与网络流．北京：中国林业出版社，2000． 参考书目： [1] Bela Bollobas．Modern Graph Theory（现代图论，影印版）．北京：科学出版社，2001． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学出版社，2003． [3] 谢金星、邢文训．网络优化．北京：清华大学出版社．2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学出版社，2000． [5] 三味工作室．SPSS V10.0 for Windows 实用基础教程．北京：北京希望电子出版社2001． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．MATLAB程序设计语言．西安：西安电子科技大学出版社，1997．八、教学基本内容及要求 第一章图的基本概念 1．教学基本要求 掌握的图的基本概念、特殊图概念，了解最短路问题。 2．教学具体内容 图的基本概念，路和圈，最短路问题。
最短路问题及应用 摘要:主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法以及这两种算法在实际问题中的应用和比较。 关键词：最短路获克斯特拉(Dijkstra)，弗罗伊德(Floyd)算法 1.引言 图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数 学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等。这些古老的难题，当时吸引了很多学者的注意。在这些问题研究的基础上又继续提出了著名的四色猜想 和汉米尔顿（环游世界）数学难题。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学 等各个领域的问题时，发挥出越来越大的作用在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点 间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学 与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2.最短路算法 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的，该ij 算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短
最短路问题(short-path problem) 若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径） 1、Dijkstra算法： 用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度 代码： procedure dijkstra（v0：longint）；//v0为起点做一次dijkstra begin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongint for i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里 visit[v0]:=true;//已经连接v0结点 for i:=1 to n-1 do//剩下n-1个节点未加入路径里； begin min:=maxlongint;//初始化min for j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小 begin min:=d[j];k:=j;end; visit[k]:=true;//连接进去 for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值， if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k]; end; writeln(d[n]);//结点v0到结点n的最短路。 思考：在实现步骤时，效率较低需要O(n)，使总复杂度达到O(n^2)。对此可以考虑用堆这种数据结构进行优化，使此步骤复杂度降为O(log(n))(总复杂度降为O(n log(n))。 实现：1. 将与源点相连的点加入堆（小根堆），并调整堆。 2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。 3. 处理与u相邻（即下一个）未被访问过的，满足三角不等式的顶点 1):若该点在堆里，更新距离，并调整该元素在堆中的位置。 2):若该点不在堆里，加入堆，更新堆。 4. 若取到的u为终点，结束算法；否则重复步骤2、3。 **优化代码：(DIJKSTRA+HEAP) program SSSP;{single source shortest path} {假设一个图的最大节点数为1000，所有运算在integer范围内} {程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度} const maxn=1000;{最大节点数} var n:integer;{节点个数} list:array[1..maxn,1..maxn] of integer;{邻接矩阵，表示边的长度}
关于最短路问题算法的一点思考 最短路问题，实际上是P95。也就是我们用一个算法解决SP问题时，就是在找这个加权图G中从s到t的P（s，t）中边权之和最小的P*(s,t). 由定义就可以看出，实际生活中经常有最短路问题的例子。例如： 实例1.某公司在六个城市s,t,a,b都有分公司，公司成员经常往来于它们之间，已知从Vi到Vj的直达航班票价由下述矩阵的第i行，第j列元素给出（∞表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。 图+矩阵 实例2.如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道。若有一批货物要从s号顶点运往t号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？ 图+矩阵 因此怎么样快速又精确的求解一个最短路问题就显得至关重要。下面我们来介绍几种解决SP问题的有效途径。 一、把求最短路问题转化为LP问题 P95 二、最短路问题的原始对偶算法：Dijkstra算法 Pdf最短路+课本P138 综上，即为Dijkstra算法，它的有效实施体现在：P161 对Dijkstra算法的一点思考： 1.关于Dijkstra算法，书中的例子定义了一个使用范围，即寻求有向图中，从一固定顶点到其余各点的最短路径。那么一个简单的推广就是在于，对于无向图或者混合图的情况Dijkstra算法还能否使用？答案应该是肯定的。也就是说，实例2中无论是单行道，双行道的情况都是可以应用Dijkstra算法进行求解的。 2. 作为学习图论的一名学生，Dijkstra算法的本质可以说就是在一个图中，进行标号,每次迭代产生一个永久标号, 从而生长一颗以s为根的最短路树,在这颗树上每个顶点与根s 节点之间的路径皆为最短路径. 3.Dijkstra算法明确要求权（费用）非负，这无疑会限制一些是实际生活中的例子进行求解，若出现的边权为负的情况，Dijkstra算法就要进行修改。并且，如果我们对Dijkstra算法进行编程，即使根据书中拟Algol语言的提示以我现有的水平也根本写不出Matlab的高级程序语言。但是有另外一种算法有效的避免了这个麻烦，它的逻辑更为简单，并允许网络中的弧有负权，能探测网络中负费用圈，与一般的原始对偶算法不同。 三、Floyd-Warshall算法 P164 并且，有一点比较吸引我的地方是在于Floyd-Warshall算法的逻辑较为简单，我可以跟据课本上拟Algol语言，编写出一部分Matlab的程序，但是因为编译程序的水平的限制，每次运行的时候都会出现不同的错误。在与计算数学的同学进行讨论的时候，因为他们偏重绘图而我们偏重优化，导致也为得出有效的解决措施。
我写的Dijkstra最短路算法通用Matlab程序%dijkstra最短路算法通用程序，用于求从起始点s到其它各点的最短路 %D为赋权邻接矩阵，d为s到其它各点最短路径的长度，DD记载了最短路径生成树function [d,DD]=dijkstra_aiwa(D,s) [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0; dd=zeros(1,m); dd(1,s)=1; y=s; DD=zeros(m,m); DD(y,y)=1; counter=1; while length(find(dd==1)) for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 《最短路径问题》的反思及应用 我们知道，有效地开发和利用课本，对于学生的学习具有重要的意义。学生对于课本上例题或习题能否吃透，直接影响着学生的学习效果。因此教师要引导学生挖掘教材，引导学生进行反思，从中领悟问题解决过程的数学内涵。 有这样一个问题： 如图1所示，牧马人从A 地出发，到一条笔直的河边l 饮马，然后到B 地。牧马人到河边的什么地方饮马，可使所走的路径最短? 分析 我们把河边近似看做一条直线l (如图2)，P 为直线l 上的一个动点，那么，上面的问题可以转化为：当点P 在直线l 的什么位置时，AP 与PB 的和最小。 如图3所示，作点B 关于直线l 的对称点'B ，连接'AB ，交直线l 于点P ，则点P 就是牧马人到河边饮马的位置。事实上，点'B 与点A 的线段'AB 最短，由对称性质知，'PB PB =，因为''PA PB PA PB AB +=+=，即点P 到点A 、B 的距离之和最小。 上述路径问题，是利用轴对称的性质，通过等线段代换，将所求路线长转化为两定点之间的距离，基本思路是运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长。从解题过程不难看出，本题蕴含着三个数学思想方法:数学模型思想，转化思想，对称思想。如果学生一旦认识或明白这些思想方法，就能举一反三，再复杂的问题也会迎刃而解。 一、基本应用 如图4，点O 是矩形ABCD 的中心，E 是AB 上的点，沿CE 折叠后，点B 恰好与点O 重合，若3BC =，则折痕CE 的长为多少? 分析 沿CE 折叠后，点B 恰好与点O 重合，则点B 、点O 关于直线CE 对称， 3CO CB ==，1122 ACB ∠=∠=∠，点O 是矩形ABCD 的中心，知26AC CO ==。所以12302 ACB ∠=∠=?，又在Rt CBE ∠中，30BCE ∠=?，3BC =，若设BE x =，则 2CE x =，得222(2)3x x -=，13x =23x -（舍去），所以223CE x == 二、拓展应用 如图5两条公路BA 、BC 相交于点B ，在两条公路之间的P 点有一个油库，若要在公 Floyd最短路径算法 在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层的时候好像也遇到过这个问题，记不请了... 但是书本上一律采取的是Dijkstra算法，通过Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味，采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下： 如果有一个矩阵D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序，通过这个距离矩阵D，把任意两个城市之间的最短与其行径的路径找出来。 我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n 是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i 到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的话，会发现是有问题的。 for(int i=0; i 第25卷第3期 Vol .25 No .3长春师范学院学报(自然科学版)Journal of Changchun Normal University (Natural Science )2006年6月Jun .2006 最短路问题在运输网络中的应用 李 玲 (陕西工业职业技术学院,陕西咸阳 712000) [摘 要]最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化 问题都可以转化为最短路问题来求解。本文重在研究公路网络运输中的最短路问题。 [关键词]最短路;网络运输;网络优化;动态规划 [中图分类号]O221 [文献标识码]A [文章编号]1008-178X (2006)03-0058-04 [收稿日期]2006-02-01 [作者简介]李 玲(1977-),女,陕西商洛人,陕西工业职业技术学院教师,从事计算机专业基础课教学研究。 1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图(w ij ≥0)的有效算法是由荷兰著名计算机专家E .W .Dijkstra [1]在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解 图G 中一特定点到其它各顶点的最短路。后来海斯[2]在Dijkstra 算法的基础之上提出了海斯算法。但这两种 算法都不能解决含有负权的图的最短路问题。因此由Ford [3]提出了Ford 算法,它能有效地解决含有负权的最 短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在(w ij ≥0)的情况下选择Dijkstra 算法。 定义1[4]若图G =G (V ,E )中各边e 都赋有一个实数W (e ),称为边e 的权,则称这种图为赋权图,记为G =G (V ,E ,W )。 定义2[5] 若图G =G (V ,E )是赋权图且W (e )≥0,e ∈E (G ),若u 是v i 到v j 的路W (u )的权,则称W (u )为u 的长,长最小的v i 到v j 的路W (u )称为最短路。 若要找出从v 1到v n 的通路u ,使全长最短,即min W (u )=∑e ij ∈u W (e )。2 最短路问题算法的基本思想及基本步骤 在诸多算法中(w ij ≥0)最经典的算法当属Dijkstra 算法,该算法的基本思想是动态规划[6]最优原理,即最短路线上任意两点间的路线也是最短。因此,若v i 到v j 的最短路线经过v k ,则v i 到v k 以及v k 到v j 的部分都是相应的最短路线。 基本步骤: 令 s ={v 1},i =1, s ={v 2,v 3,…,v n } 并令 W (v 1)=0 T (v j )=∞,v j ∈ s ①对v j ∈ s ,求min {T (v j ),W (v i )+w ij }=T (v j )。 ②求min v j ∈ s {T (v j )}得T (v k ),使T (v k )=min v j ∈ s {T (v j )} 湖北大学 本科毕业论文（设计） 题目最短路径算法及其应用 姓名学号 专业年级 指导教师职称 2011年 4月 20 日 目录 绪论 (1) 1 图的基本概念 (1) 1.1 图的相关定义 (1) 1.2 图的存储结构 (2) 1.2.1 邻接矩阵的表示 (2) 1.2.2 邻接矩阵的相关结论 (3) 2 最短路径问题 (3) 2.1 最短路径 (4) 2.2 最短路径算法 (4) 2.2.1Dijkstra算法 (4) 2.2.2Floyd算法 (5) 3 应用举例 (5) 3.1 Dijkstra算法在公交网络中的应用 (5) 3.1.1 实际问题描述 (5) 3.1.2 数学模型建立 (5) 3.1.3 实际问题抽象化 (6) 3.1.4 算法应用 (6) 3.2 Floyd算法在物流中心选址的应用 (7) 3.2.1 问题描述与数学建模 (7) 3.2.2 实际问题抽象化 (7) 3.2.3 算法应用 (8) 参考文献 (10) 附录 (11) 最短路径算法及其应用 摘要 最短路径算法的研究是计算机科学研究的热门话题，它不仅具有重要的理论意义，而且具有重要的实用价值。最短路径问题有广泛的应用，比如在交通运输系统、应急救助系统、电子导航系统等研究领域。最短路径问题又可以引申为最快路径问题、最低费用问题等，但它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra和Floyd算法是目前最短路径问题采用的理论基础。本文主要对Dijkstra和Floyd算法进行阐述和分析，然后运用这两个算法解决两个简单的实际问题。 【关键字】最短路径 Dijkstra算法 Floyd算法图论 最短路问题与拱桥问题（讲义） 课前预习 1.常用的6组勾股数：___________；__________；___________； ___________；__________；___________． 2.一个门框的尺寸如图所示，一块长3m ，宽2.2m 的薄木板 _______ （能或不能）从门框通过． 3.读一读，做一做 小聪郊游时发现了一个有趣的问题：有一只蚂蚁从易拉罐底部爬向易拉罐顶部的罐口处喝饮料，在侧面留下了其爬行的轨迹．小聪观察后发现，蚂蚁爬行的路径是一条曲线，小聪想知道蚂蚁具体爬行了多长，于是邀请小明一起来研究这个问题．经过一番讨论，小聪和小明分别准备尝试用两种方法来进行测量． 方案一：小聪准备用一根绳子沿着蚂蚁爬过的轨迹来进行测量，然后再借助绳子的长度来估计爬行的路程，如图1．方案二：小明准备将易拉罐侧面剪开，然后用尺子直接测量蚂蚁爬行的路程．小明剪开易拉罐侧面，将其展开后发现，蚂蚁爬行的路径竟然是一条笔直的线段，如图2． 请你选一张长方形纸片，画出他的对角线，然后卷成一个圆柱，并参照小聪和小明的方法，动手测量一下这条线的长度．图1 图2 知识点睛 蚂蚁爬最短路问题处理思路： （1）________________________； （2）找点，连线； （3）构造__________，利用__________进行计算． 精讲精练 1.有这样一个有趣的问题：如图所示，圆柱的高等于8cm，底 面半径等于2cm．在圆柱的下底面的A点处有一只蚂蚁，它想吃到上底面上与A相对的B点处的食物，则蚂蚁沿圆柱的侧面爬行的最短路程是__________．（π取整数3） 2.如图，一根藤蔓一晚上生长的长度是沿树干爬一圈后由点A 上升到点B，已知AB=5cm，树干的直径为4cm．你能计算出藤蔓一晚上生长的最短长度吗？（π取整数3） 大连海事大学 图论论文 姓名： 学号： 专业：计算机科学与技术 院系：信息科学技术2009级 摘要： 主要介绍最短路的两种算法，迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。以及这两种算法在实际问题中的应用和比较。 关键字：图论，最短路径，树，生成树，迪杰斯特拉(Dijkstra)，弗罗伊德(Floyd)算法 最短路问题及其应用 1 引言 图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等．这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2 最短路 2.1 最短路的定义 w≥对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()0 ij 的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因 本科生毕业设计（论文）题目：线性表的设计和实现 学生姓名：张三 学号： 1153 院系：基础科学学院信息技术系 专业年级：2012级信息与计算科学专业 指导教师：李四 年月日 摘要 随着现代物流业的发展，如何优化和配置物流的运输路径成为了一个热点的问题。其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径，使其距离最短。为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法，分析了它们的适用范围以及时间复杂度。最后，对一个具体的航空公司物流配送问题进行了求解，得到了理论最优路径。 关键词：最短路径问题；DIJKSTRA算法；物流运输 ABSTRACT With the development of modern logistics industry, how to optimize and configure the transport path of logistics has become a hot issue. Among them, the most representative problem is how to select the appropriate path between two points in a road network to minimize the distance. In order to solve this problem, this paper introduces two most common shortest path solutions ——Dijkstra algorithm and Floyd algorithm, and analyzes their application range and time complexity. Finally, a specific airline logistics distribution problem is solved, and the theoretical optimal path is obtained. Keywords：Minimum path problem；Dijkstra algorithm；Logistics transportation 最短路径算法及应用 乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 一种可能的方法就是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。那么我们很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是不值得考虑的。 在这一章中，我们将阐明如何有效地解决这类问题。在最短路径问题中，给出的是一有向加权图G＝（V，E，W），其中V为顶点集，E为有向边集，W为边上的权集。最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。 一、单源最短路径问题 所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V 到V中的每个结点的最短路径。 首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。 （一）Dijkstra算法 对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。 例1 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。 Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个 点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P 标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T 标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。 在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例1中，s=1。因为所有Wij≥0，故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1, v2), (v1, v3)和(v1, v4)。如果某人从v1出发沿(v1, v2)到达v2，这时需要d(v1, v1)+w12=6单位的费用；如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用；类似地，若沿(v1, v4)到达v4，这时需要d(v1, v1)+w14=1单位的费用。因为min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v1)+w14}= d(v1, v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4)，d(v1, v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1, v4)，则必是先从v1沿(v1, v2)到达v2，或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij≥0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3，需要的费用分别为6与3，而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v4)+w46}= d(v1, v1)+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1, v3)，d(v1, v3)=3。这样又可以使点v3变成具P 标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。 在下述的Dijstra方法具体步骤中，用P，T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个λ值，算法终止时λ(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果λ(v)=∞，表示图G中不含从Vs到v的路；λ(Vs)=0。 Dijstra方法的具体步骤： {初始化} i=0 S0={Vs}，P(Vs)=0 λ(Vs)=0 对每一个v<>Vs，令T(v)=+ ∞，λ(v)=+ ∞， k=s {开始} ①如果Si=V，算法终止，这时，每个v∈Si，d(Vs,v)=P(v)；否则转入② ②考察每个使(Vk,vj)∈E且vj Si的点vj。 如果T(vj)>P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把λ(vj)修改为k。 ③令 如果，则把的标号变为P标号，令 ，k=ji，i=i+1，转①，否则终止，这时对每一个v∈Si，d(vs,v)=P(v)，最短路径问题的反思及应用
最短路算法程序
最短路问题在运输网络中的应用
最短路径算法及其应用
最短路问题与拱桥问题(讲义及答案).
最短路问题及其应用——最短路径
最短路径算法在物流运输中的应用
(完整word版)最短路径算法附应用
相关主题
文本预览