韦艳肖

摘 要：举例说明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=+∞。……