资源描述：
《两类经典算法求最短路问题剖析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
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
