详谈Dijkstra算法

本文由单源最短路径路径问题开始，而后描述Bellman-Ford算法，到具体阐述Dijkstra算法，阐述详细剖析Dijkstra算法的每一个步骤，教你彻底理解此Dijkstra算法。

一、单源最短路径问题

我们知道，单源最短路径问题：已知图G=(V，E)，要求找出从某个定源顶点s<-V，到每个v<-V的最短路径。简单来说，就是一个图G中，找到一个定点s，然后以s为起点，要求找出s到图G中其余各个点的最短距离或路径。

此单源最短路径问题有以下几个变形：

I、  单终点最短路径问题： 每个顶点v到指定终点t的最短路径问题。即单源最短路径问题的相对问题。

II、 单对顶点最短路径问题：给定顶点u和v，找出从u到v的一条最短路径。

III、每对顶点间最短路径问题：

针对任意每俩个顶点u和v，找出从u到v的最短路径。最简单的想法是，将每个顶点作为源点，运行一次单源算法即可以解决这个问题。当然，还有更好的办法。 

二、Bellman-Ford 算法

1、回路问题

一条最短路径不能包含负权回路，也不能包含正权回路。一些最短路径的算法，如Dijkstra 算法，要求图中所有的边的权值都是非负的，如在公路地图上，找一条从定点s到目的顶点v的最短路径问题。

2、Bellman-Ford 算法

而Bellman-Ford 算法，则允许输入图中存在负权边，只要不存在从源点可达的负权回路，即可。简单的说，图中可以存在负权边，但此条负权边，构不成负权回路，不影响回路的形成。且，Bellman-Ford 算法本身，便是可判断图中是否存在从源点可达的负权回路，若存在负权回路，算法返回FALSE,若不存在，返回TRUE。

Bellman-Ford 算法的具体描述

BELLMAN-FORD(G, w, s)

INITIALIZE-SINGLE-SOURCE(G, s)   //对每个顶点初始化 ，O(V)   
for i ← 1 to |V[G]| - 1  
  do for each edge (u, v) ∈ E[G]  
do RELAX(u, v, w)    //针对每个顶点(V-1个)，都运用松弛技术O(E)，计为O（(v-1)*E)）  
for each edge (u, v) ∈ E[G]  
do if d[v] > d[u] + w(u, v)  
then return FALSE     //检测图中每条边，判断是否包含负权回路，  
                                    //若d[v]>d[u]+w(u，v)，则表示包含，返回FALSE，  
return TRUE                      //不包含负权回路，返回TRUE  

Bellman-Ford 算法的时间复杂度，由上可得为O（V*E）。

3、关于判断图中是否包含负权回路的问题：

根据定理，我们假定，u是v的父辈，或父母，那么，当G(V,E)是一个有向图或无向图(且不包含任何负权回路)，s<-V，s为G的任意一个顶点，则对任意边(u，v)<-V，有     

d[s，v] <= d[s，u]+1

此定理的详细证明，可参考算法导论一书上，第22章中引理22.1的证明。或者根据第24章中通过三角不等式论证Bellman-Ford算法的正确性，也可得出上述定理的变形。

即假设图G中不包含负权回路，可证得

d[v]=$(s，u)  
      <=$(s，u)+w(u，v)  //根据三角不等式  
      =d[u]+w[u，v] 

所以，在不包含负权回路的图中，是可以得出d[v]<=d[u]+w(u，v)。

于是，就不难理解，在上述Bellman-Ford 算法中， if d[v] > d[u]+w(u，v)，=> 包含负权回路，返回FASLE

else if =>不包含负权回路，返回TRUE。

ok，咱们，接下来，立马切入Dijkstra 算法。

三、深入浅出，彻底解剖Dijkstra 算法

I、松弛技术RELAX的介绍

Dijkstra 算法使用了松弛技术，对每个顶点v<-V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，
称为最短路径的估计。

首先，得用O（V）的时间，来对最短路径的估计，和对前驱进行初始化工作。

INITIALIZE-SINGLE-SOURCE(G, s)  
 for each vertex v ∈ V[G]  
  do d[v] ← ∞  
   π[v] ← NIL      //O（V）  
d[s] 0  
 
RELAX(u, v, w)  
if d[v] > d[u] + w(u, v)  
 then d[v] ← d[u] + w(u, v)  
  π[v] ← u        //O（E）图。 

II、Dijkstra 算法

此Dijkstra 算法分三个步骤，INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX，调用此减小关键字的操作)。

DIJKSTRA(G, w, s)  
 INITIALIZE-SINGLE-SOURCE(G, s)    //对每个顶点初始化 ，O(V)   
 S ← Ø  
 Q ← V[G]            //INSERT，O(1)  
 while Q ≠ Ø  
   do u ← EXTRACT-MIN(Q)        //简单的O(V*V)；二叉/项堆，和FIB-HEAP的话，则都为O(V*lgV)。      
 S ← S ∪{u}  
     for each vertex v ∈ Adj[u]  
          do RELAX(u, v, w)      //简单方式:O(E)，二叉/项堆，E*O(lgV)，FIB-HEAP，E*O(1)。 

四、Dijkstra 算法的运行时间

在继续阐述之前，得先声明一个问题，DIJKSTRA（G，w，s）算法中的第5行，EXTRACT-MIN(Q)，最小优先队列的具体实现。而Dijkstra 算法的运行时间，则与此最小优先队列的采取何种具体实现，有关。

最小优先队列三种实现方法：

1、利用从1至|V| 编好号的顶点，简单地将每一个d[v]存入一个数组中对应的第v项，如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的运行时间为O(V^2+E)。

2、如果是二叉/项堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，所以，Dijkstra 算法的运行时间为O(V*lgV+E*lgV)，若所有顶点都是从源点可达的话，O（(V+E)*lgV）=O（E*lgV）。当是稀疏图时，则E=O(V^2/lgV)，此Dijkstra 算法的运行时间为O(V^2)。

3、采用斐波那契堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，所以，此Dijkstra 算法的运行时间即为O(V*lgV+E)。

综上所述，此最小优先队列的三种实现方法比较如下：