Dijkstra 算法

Dijkstra's algorithm

     -- 贪婪技术的一种经典算法，戴克斯特拉算法（维基说法）

---

# 算法逻辑

算法描述 Dijkstra (G, s)

          // 单起点最短路径的Dijstra算法

          // 输入: 具非负权重加权连通图 G = < V, E> 以及它的顶点s

          // 输出: 对于V中的每一个顶点v来说, 从s到v的最短路径的长度dv

          // 以及路径上的倒数第二个顶点pv

          Initialize(Q)     // 将顶点优先队列初始化为空

          for V中每一个顶点 v do

               dv = -1; pv = null;

               Insert(Q, v, dv);     // 初始化优先队列中顶点的优先级

          ds = 0; Decrease(Q, s, ds);

          Vt = {} // 初始化为空

          for i = 0 to |V| - 1 do

               u* = DeleteMin(Q);     //删除优先级最小的元素

               Vt = Vt + { u* };

               for V - Vt 中每一个和u*相邻的顶点u do

                    if du* + w(u*, u) < du

                         du = du* + w(u*, u);

                         pu = u*;

                         Decrease(Q, u, du);

# 算法效率

分析该算法的时间复杂度，假设对应的连通图边数 m 和顶点数 n 。

1， 最简单实现方法，以一个链表或者数组来存储所有顶点的集合Q，而搜索Q中权值最小元素操作DeleteMin只需线性搜索为复杂度O(n)。该算法整体的时间复杂度是 O(n^2)。

2， 用邻接表来更有效的实现该算法，同时以二叉树结构作为优先队列存Q，则搜索权值最小元素DeleteMin时间复杂度为Q(log n)，此时该算法整体的时间复杂度为O((m + n)log n)，

# 示例说明

（还是伪码，从代码提炼出来的伪码，这样看起来应该比较浅显易懂。）

void Dijkstra (Graph& G)

{

Queue Q; Path P;

InitQueuePath(Q, P);

for (int s=0; s< G.points;s++) {

Decrease(Q, s, 0);

for (int i=0; i < G.points-1; i++) {

int u = DeleteMin(Q, G.flag, G.points);

if (u==-1)

break;

for (int j=0; j< G.points; j++) {

if ( G.flag[j]==false && ((__int64)Q[u]+G.A[u][j])<Q[j]) {

P[j] = u;

Decrease(Q, j, Q[u]+G.A[u][j]);

}

}

}

for (int i=0; i < G.points; i++)

G.A[i][s] = G.A[s][i] = Q[i];

}

}

完整的C++示例代码存放在github。

# 引用扩展

参见维基上伪码描述如下：

在下面的算法中，u := Extract_Min(Q) 在顶点集合 Q 中搜索有最小的 d[u] 值的顶点 u。这个顶点被从集合 Q 中删除并返回给用户。

function Dijkstra(G, w, s)
     for each vertex v in V[G]                        // 初始化
             d[v] := infinity                         // 将各点的已知最短距离先设置成无穷大
             previous[v] := undefined                 // 各点的已知最短路径上的前趋都未知
     d[s] := 0                                        // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
     S := empty set
     Q := set of all vertices
     while Q is not an empty set                      // Dijkstra演算法主體
             u := Extract_Min(Q)
             S.append(u)
             for each edge outgoing from u as (u,v)
                      if d[v] > d[u] + w(u,v)         // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
                              d[v] := d[u] + w(u,v)   // 更新路径长度到更小的那个和值。
                              previous[v] := u        // 记录前趋顶点

如果我们只对在 s 和 t 之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足 u = t 的话终止程序。

通过推导可知，为了记录最佳路径的轨迹，我们只需记录该路径上每个点的前趋，即可通过迭代来回溯出 s 到 t 的最短路径（当然，使用后继节点来存储亦可。但那需要修改代码）：

 s := empty sequence 

 u := t

 while defined u                                        

       insert u to the beginning of S

       u := previous[u]      //previous数组即为上文中的p

现在序列 S 就是从 s 到 t 的最短路径的顶点集。

关于“Dijkstra 算法”更详细的文字描述可以参见维基百科，百度百科。