最短路径算法研究

李鲁平

摘要：最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要對其中的两种：Dijkstra和Floyd-Warshall进行研究和分析实现。

关键词：算法；动态规划；最短路径；编程开发

0 引言

在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：

（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

（2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

（3）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

（4）全局最短路径问题：求图中所有的最短路径。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、SPFA算法。Floyd-Warshall算法是求多源、无负权边的最短路，用矩阵记录图，时效性较差，时间复杂度O（V^3）。Dijkstra算法是求单源、无负权的最短路的算法，时效性较好，时间复杂度为O（V*（V+E）），可以用优先队列进行优化，优化后时间复杂度变为O（v*lgn）。Bellman-Ford算法求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（V*E）。SPFA算法是对Bellman-Ford算法的队列优化，时效性相对好，时间复杂度O（kE）。本文主要研究Dijkstra和Floyd-Warshall算法细节。

1. Dijkstra算法

Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发现的单源最短路径算法，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。该性质描述为：如果P（i，j）={Vi...Vk...Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P（k，s）必定是从k到s的最短路径。

证明该最优子结构为，假设P（i，j）={Vi...Vk…Vs...Vj}是从顶点i到j的最短路径，则有P（i，j）=P（i，k）+P（k，s）+P（s，j）。而P（k，s）不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'（k，s），那么P'（i，j）=P（i，k）+P'（k，s）+P（s，j）

由上述性质可知，如果存在一条从i到j的最短路径（Vi...Vk，Vj），Vk是Vj前面的一顶点。那么（Vi...Vk）也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根据这种思路，假设存在G=，源顶点为V0，U={V0}，dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点：

1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；

2.更新与i直接相邻顶点的dist值。（dist[j]=min{dist[j]，dist[i]+matrix[i][j]}）

3.知道U=V，停止。

2. Floyd-Warshall算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O（N3），空间复杂度为O（N2）。

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释。

从任意节点i到任意节点j的最短路径不外乎2种可能，一是直接从i到j，二是从i经过若干个节点k到j。所以，我们假设Dis（i，j）为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis（i，k） + Dis（k，j） < Dis（i，j）是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis（i，j） = Dis（i，k） + Dis（k，j），这样一来，当我们遍历完所有节点k，Dis（i，j）中记录的便是i到j的最短路径的距离。

3. 总结

Dijkstra算法是解决单源最短路径问题的贪心算法，其基本思想是设置顶点集合S并不断地做贪心选择来扩充这个集合。对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O（n）时间。这个循环需要执行n-1次，所以完成循环需要O（n2）时间。而Floyd算法的原理是动态规划，时间复杂度为O（n3），空间复杂度为O（n2），在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的堆优化版本。

参考文献

[1] 黄国瑜、叶乃菁，数据结构，清华大学出版社，2001年8月第1版

[2] 最短路径，http：//baike.baidu.com/view/349189.htm？func=retitle

[3] 李春葆，数据结构教程，清华大学出版社，2005年1月第1版

[3] Dijkstra算法，http：//baike.baidu.com/view/7839.htm