两类经典算法求最短路问题剖析

韦艳肖

摘 要：举例说明Dijkstra算法和Floyd算法求最短路问题，通过规定起点、终点、各点之间权值的大小，找出了最短路径，求出最短路长，并增加负权值、方向和闭合回路来分别研究两种算法在运算中的利弊以及适用性。

关键词：Dijkstra算法；Floyd算法；最短路

1.引言

众所周知，最短路算法有两种基本算法，一是指定的顶点之间的最短路径算法，二是所有顶点之间的最短路算法，其中所有顶点间最短路算法更具有代表性。目前，求最短路问题的方法很多，各有优劣性，而实际应用中以两类经典算法居多，分别是1959年E.W.Dijkstra提出的Dijkstra算法和1962年Floyd提出的Floyd算法。

1.1 Dijkstra算法

Dijkstra算法的基本思想是：若起点vs到终点vt的最短路经过点v1，v2，v3，则v1到vt的最短路是p1t={v1，v2，v3，vt}，v2到vt的最短路是p2t={v2，v3，vt}，v3到vt的最短路是p3t={v3，vt}，Dijkstra算法是在图上进行一种标号迭代的过程。不妨设弧（i，j）的长度为cij≥0，vi到vj的最短路记为pij，最短路长记为Lij。Dijkstra算法的基本步骤如下[1-2]：

（1）找出所有起点vi已标号，终点vj未标号的弧，集合为B={（i，j）︱vi已标号；vj未标号}，如果这样的弧不存在或已标号则计算结束。

（2）计算集合B中弧的标号：k（i，j）=b（i）+cij。

（3）b（l）=minj{k（i，j）|（i，j）∈B}，在弧的终点vl标号b（l），返回步骤（1）。

完成步骤（1）～（3）为一轮计算，每一轮计算至少得到一个点的标号，最多通过n轮计算得到最短路。

1.2 Floyd算法

Floyd算法是一种矩阵迭代方法，也是一种表格迭代方法，对于求任意点间最短路、混合图的最短路、有负权图的最短路等一般网络问题来说是比较有效的，Floyd算法的基本步骤如下[1-2]：

（1）写出vi一步到达vj的距离矩阵L1=（L（1）ij），L1也是一步到达的最短距离矩阵。如果vi 与vj之间没有关联，则令cij=+∞。

（2）计算两步最短矩阵。设vi到vj经过一个中心点vr，要两步到达vj，則vi到vj的最短距离为L（2）ij=minr{cir+crj}，最短距离矩阵为L2=（L（2）ij）。

（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）比较矩阵Lk与Lk-1，当LK=Lk-1时得到任意两点间的最短距离矩阵Lk。

2.具体应用

本节中通过具体例子，如图1，图2所示，利用Dijkstra算法和Floyd算法分别求出顶点v1到顶点v8的最短路以及最短路长。

即得出v1到v8的最短距离为18，其所对应的最小生成树和最短路线图分别如图2-8和2-9所示：

3.算法分析

综上，通过具体例子介绍和分析了Dijkstra算法和Floyd算法这两种非常经典的最短路算法。可得Dijkstra算法是主要用于解决无负权值的有向图和无向图的最短路算法，Floyd算法是通过矩阵运算来求解网络中的最短路问题的方法。这两种算法都可计算一个结点到其它结点的最短路径。Dijkstra算法是运用表上做图的方式一个一个点的添加，根据最小的权值的选择依次对各点进行标号，直到将所有的点都标上号，从而找出最短路径。而Floyd算法是首先将所有的点都标出，将各点间的权值反应在矩阵上，再用矩阵计算出最优矩阵。Dijkstra算法的优点是算法比较简单明了，不易出错，但是也有缺点，主要是步骤却非常繁琐。Floyd算法的算法虽然说有点复杂，但是效率比较高，在计算时能够节约时间。综上所述，两种算法的差别很大，但是效果却是相同的。我们在实际的运用中可以按各自的需求选择合适的方法。（作者单位：河池学院数学与统计学院）

基金项目：广西高校科学研究项目（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] 张新元.最短路问题的Seidel迭代[J].数学的实践与认识，1993，7（2）：18-21.

[7] 林华珍，周根贵.求解最短路问题的一种优化矩阵算法[J].长江大学学报（自然科学版），2007，4（4）：14-16.