资源描述:
《两类经典算法求最短路问题剖析》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、两类经典算法求最短路问题剖析摘要:举例说明Dijkstra算法和Floyd算法求最短路问题,通过规定起点、终点、各点之间权值的人小,找出了最短路径,求出最短路长,并增加负权值、方向和闭合回路来分别研究两种算法在运算中的利弊以及适用性。关键词:Dijkstra算法;Floyd算法;最短路1.引言众所周知,最短路算法有两种基本算法,一是指定的顶点Z间的最短路径算法,二是所有顶点之间的最短路算法,其中所有顶点间最短路算法更具有代表性。目前,求最短路问题的方法很多,各有优劣性,而实际应用中以两类经典算法居多,分别是1959年E.W.Dijkstra提出的Dijkstra算法
2、和1962年Floyd提出的Floyd算法。1.1Dijkstra算法Dijkstra算法的基本思想是:若起点vs到终点vt的最短路经过点vl,v2,v3,则vl到vt的最短路是plt={vl,v2,v3,vt},v2到vt的最短路是p2t={v2,v3,vt},v3到vt的最短路是p3t={v3,vt},Dijkstra算法是在图上进行一种标号迭代的过程。不妨设弧(i,j)的长度为cij20,vi到vj的最短路记为pij,最短路长记为LijoDijkstra算法的基本步骤如下[1-2]:(1)找出所有起点vi已标号,终点vj未标号的弧,集合为B二{(i,j)??v
3、i已标号;vj未标号},如果这样的弧不存在或已标号则计算结束。(1)计算集合B中弧的标号:k(i,j)=b(i)+cij。(2)b(1)=minj{k(i,j)
4、(i,j)^B},在弧的终点vl标号b(1),返回步骤(l)o完成步骤(1)〜(3)为一轮计算,每一轮计算至少得到一个点的标号,最多通过n轮计算得到最短路。1.2Floyd算法Floyd算法是一种矩阵迭代方法,也是-•种表格迭代方法,对于求任意点间最短路、混合图的最短路、有负权图的最短路等一般网络问题来说是比较有效的,Floyd算法的基本步骤如下[1-2]:(1)写出vi—步到达vj的距离矩阵L1二(L(1
5、)ij),L1也是一步到达的最短距离矩阵。如果vi与vj之间没有关联,则令cij二+8。(2)计算两步最短矩阵。设vi到vj经过一个屮心点vr,要两步到达vj,则vi到vj的最短距离为L(2)ij=minr{cir+crj},最短距离矩阵为L2二(L(2)ij)o(3)计算k步最短距离矩阵。设vi经过中间点vr到达vj,vi经过k-1步到达点vr的最短距离为L(k-1)ir,vr经过k-1步到达点vj的最短距离为L(k-1)rj,则vi经k步到达vj的最短距离为L(k)ij=minr{L(k-1)ir+L(k-1)rj},最短距离矩阵为Lk二(L(k)ij)。(4)
6、比较矩阵Lk与Lk-1,当LK=Lk-l时得到任意两点间的最短距离矩阵Lk。1.具体应用本节中通过具体例子,如图1,图2所示,利用Dijkstra算法和Floyd算法分别求出顶点vl到顶点v8的最短路以及最短路长。即得出vl到v8的最短距离为18,其所对应的最小生成树和最短路线图分别如图2-8和2-9所示:2.算法分析综上,通过具体例子介绍和分析了Dijkstra算法和Floyd算法这两种非常经典的最短路算法。可得Dijkstra算法是主要用于解决无负权值的冇向图和无向图的最短路算法,Floyd算法是通过矩阵运算來求解网络中的最短路问题的方法。这两种算法都可计算一个
7、结点到其它结点的最短路径。Dijkstra算法是运用表上做图的方式一个一个点的添加,根据最小的权值的选择依次对各点进行标号,直到将所有的点都标上号,从而找出最短路径。而Floyd算法是首先将所有的点都标出,将各点间的权值反应在矩阵上,再用矩阵计算出最优矩阵。Dijkstra算法的优点是算法比较简单明了,不易出错,但是也有缺点,主要是步骤却非常繁琐。Floyd算法的算法虽然说有点复杂,但是效率比较高,在计算时能够节约时间。综上所述,两种算法的差别很大,但是效果却是相同的。我们在实际的运用中可以按各自的需求选释合适的方法。(作者单位:河池学院数学与统计学院)基金项目:广
8、西高校科学研究项目(201010LX481),广西高等教育教学改革工程项目(2015JGA552)参考文献:[1]严蔚敏•吴伟民•数据结构(C语言)[M].北京:清华人学大学出版社,2007.[2]王桂平•王衍•任嘉辰•图论算法理论、实现及应用[M].北京:北京大学出版,2011.[3]王朝瑞•图论[M].北京:北京理工大学出版社,2002.[4]严寒冰等•基于GIS的城市道路网最短路径算法探讨•计算机学报,2000,23(2):210-215・[5]徐凤生•最短路径的求解算法[J]・计算机应用,2004,24(5):88-89.[6]张新元•最短路问题的Sei