戴克斯特拉算法

戴克斯特拉算法
戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。
概况
类别	搜索算法 贪心算法 动态规划
数据结构	图 堆/优先队列（算法优化）
复杂度
最坏时间复杂度	$O(|E|+|V|\log |V|)$（使用斐波那契堆优化的戴克斯特拉算法）
空间复杂度	$O(|E|+|V|)$（使用邻接表存储边的情况）
相关变量的定义
$|E|$代表图中边数，$|V|$代表图中结点个数，$Q$为目前所有实际最短路径值不确定结点的集合，$S$为目前所有实际最短路径值确定结点的集合，$d[]$为到某点的最短路径估计，$\delta$为到某点的最短路径实际值，$|L|$为边集中边的最大权值。

戴克斯特拉算法（英语：Dijkstra's algorithm），又称迪杰斯特拉算法、Dijkstra算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。

该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。

该算法解决了图 $G=\langle V,E\rangle$上带权的单源最短路径问题。具体来说，戴克斯特拉算法设置了一顶点集合$S$，在集合$S$中所有的顶点与源点$s$之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点$u\in {V-S}$并将$u$加入$S$中。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。

应当注意，绝大多数的戴克斯特拉算法不能有效处理带有负权边的图。

戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是最良优先搜索的一个特例。

描述

上图为戴克斯特拉算法应用示意图。
起点以左下角的红点，目标是右上角的绿点，中间灰色的倒L型为障碍物。蓝色空圈表示"暂定"，用以搜索下一步；已经填充颜色的表示探访过，图中颜色以红到绿，越绿表示离起点越远。所有结点都被均匀探索。

戴克斯特拉算法通过保留目前为止所找到的每个顶点$v\in V$从$s$到$v$的最短路径来工作。初始时，原点$s$的路径权重被赋为 0 （即原点的实际最短路径=0）。同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径。当算法结束时，$d[v]$ 中存储的便是从$s$到$v$的最短路径，或者如果路径不存在的话是无穷大。

松弛操作是戴克斯特拉算法的基础操作：如果存在一条从$u$到$v$的边，那么从$s$到$v$的一条新路径是将边$w(u,v)\in E$添加到从$s$到$u$的路径尾部来拓展一条从$s$到$v$的路径。这条路径的长度是$d[u]+w(u,v)$。如果这个值比目前已知的$d[v]$的值要小，那么可以用这个值来替代当前$d[v]$中的值。松弛边的操作一直执行到所有的$d[v]$都代表从$s$到$v$的最短路径的长度值。

算法维护两个顶点集合$S$和$Q$。集合$S$保留所有已知实际最短路径值的顶点，而集合$Q$则保留其他所有顶点。集合$S$初始状态为空，而后每一步都有一个顶点从$Q$移动到$S$。这个被选择的顶点是$Q$中拥有最小的$d[u]$值的顶点。当一个顶点$u$从$Q$中转移到了$S$中，算法对$u$的每条外接边$w(u,v)$进行松弛。

《算法导论》中给出了以下伪代码：该伪代码计算并保留图$G$中原点$s$到每一顶点$v$的最短距离$d[v]$。其中，函数$Extract-Min(Q)$将顶点集合$Q$中有最小$d[u]$值的顶点$u$从$Q$中删除并返回$u$。

 1  function Dijkstra(G, w, s)
 2   INITIALIZE-SINGLE-SOURCE(G, s)                //实际上的操作是将每个除原点外的顶点的$d[v]$置为无穷大，$d[s]=0$
 3   $S\leftarrow \emptyset$
 4   $Q\leftarrow s$                                //$Q$是顶点$V$的一个优先队列，以顶点的最短路径估计排序
 5   while($Q\not =\emptyset$)
 6       do $u\leftarrow EXTRACT-MIN(Q)$          //选取$u$为$Q$中最短路径估计最小的顶点
 7       $S\leftarrow S\cup u$
 8       for each vertex v $\in Adj[u]$
 9            do RELAX(u, v, w)            //松弛成功的结点会被加入到队列中

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

在肯尼·罗森所著的《离散数学及其应用》中给出了如下的另一份伪代码：

 1 procedure Dijkstra(G：边全为正权的图）
 2   {G带有顶点$a=v_{0},v_{1},v_{2}...$和若干边$w(v_{i},v_{j})$}
 3    for $i:=1$ to n
 4       $D(v_{i}):=\infty$
 5    $D(a):=0$
 6    $S:=\emptyset$
 7    while $z\notin S$
 8    begin
 9          $u:=$不属于$S$的$D(u)$最小的一个顶点
 10        $S:=S\cup \{u\}$
 11        for 所有不属于$S$的顶点$v$
 12            if $D(u)+w(u,v)<D(v)$ then $D(v):=D(u)+w(u,v)$
 13    end{$D(z)=$从a到z的最短路长度}

在该 算法演示页面 （页面存档备份，存于互联网档案馆），可以自定义节点，边的权重等信息，然后观察算法每一步的执行过程。

时间复杂度

我们可以用大O符号将该算法的运行时间表示为边数$|E|$和顶点数$|V|$的函数。

对于任何基于顶点集$Q$的实现，算法的运行时间是$O(|E|\cdot dk_{Q}+|V|\cdot em_{Q})$，其中$dk_{Q}$和$em_{Q}$分别表示完成键的降序排列时间和从$Q$中提取最小键值的时间。

对于没有任何优化的戴克斯特拉算法，实际上等价于每次遍历了整个图的所有结点来找到Q中满足条件的元素（即寻找最小的顶点是$O(|V|)$的），此外实际上还需要遍历所有的边一遍，因此算法的复杂度是$O(|V|^{2}+|E|)$。

对于边数少于$|V|^{2}$的稀疏图来说，可以用邻接表来更有效的实现该算法。

可以使用一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点（$Extract-Min$）以优化算法。当用到二叉堆的时候，算法所需的时间为$O((|E|+|V|)\log |V|)$，斐波纳契堆能提高一些性能，让算法运行时间达到$O(|E|+|V|\log |V|)$。然而，使用斐波纳契堆进行编程，有时会由于算法常数过大而导致速度没有显著提高。

下面是一些戴克斯特拉算法经典实现的复杂度比较：

算法	最坏时间复杂度	发现者（按照论文发表时间从前向后排序）
使用邻接表的戴克斯特拉算法	$O(|V|^{2})$	莱索雷克及格雷等人，艾兹赫尔·戴克斯特拉，明蒂，怀廷及希利尔
使用二叉堆优化的戴克斯特拉算法	$O((|E|+|V|)\log |V|)$	唐纳德·约翰逊
使用斐波那契堆优化的戴克斯特拉算法	$O(|E|+|V|\log |V|)$	迈克尔·弗雷德曼及罗伯特·塔扬
	$O(|E|\log \log |L|)$	唐纳德·约翰逊，洛夫·卡尔松及帕特里西奥·波夫莱特

正确性证明

艾兹赫尔·戴克斯特拉，戴克斯特拉算法的发现者

戴克斯特拉本人在他的论文中给出了一份简单的证明。

《算法导论》使用循环不变式（数学归纳法）给出了如下的一份证明：

已知一带权图$G=<V,E>$，其加权函数$w$的值非负，源点为$s$。对该图运行戴克斯特拉算法，对所有$u\in V$有$d[u]=\delta (s,u)$。其中$d[u]$表示u点的最短路径估计，$\delta (s,u)$表示$s$到$u$点的最短路径。

证明：证明如下的循环不变式成立即可：在每次执行EXTRACT-MIN时，对每个顶点$u\in S$，有$d[u]=\delta (s,u)$成立即可。由于上界性质，在$u$加入了$S$之后，一旦有$d[u]=\delta (s,u)$，则在后面的每次循环中都不会改变这个性质。

初始化：第一次循环前，$S=\emptyset$，因此循环不变式显然成立。

保持：实际上要证明每一轮循环中加入到$S$中的结点满足$d[u]=\delta (s,u)$。利用反证法，假设$u$是第一个不满足此条件的结点，考虑循环开始前的状况，首先$u$一定不等于$s$，这是显然的。其次$s$一定有到$u$的路径，否则路径为无穷大。那么假设在$u$进入时，有最短路径$p=s->u$，假设该路径上存在两个点$x$，$y$。$y\in V-S$、$x\in S$，且x是y的前驱，路径$p$可以分解为$s-p_{1}->x->y-p_{2}->u$（此处$-p_{1}->$表示经过$p_{1}$这条路径，后同），其中路径$p_{1}$和路径$p_{2}$可以为空。由于$u$是第一个不满足$d[u]=\delta (s,u)$的，又因为$x$是满足该条件的，而且$(x,y)$一定已经被松弛过了，所以$y$是满足该条件的。

现在只需要推出矛盾，即可证明u不存在：$y$在$u$之前出现，而且图中所有权值非负，因此有$\delta (s,y)\leq \delta (s,u)$，所以：
$d[y]\leq \delta (s,y)\leq \delta (s,u)\leq d[u]$，但是由于$u$和$y$同时在$V-S$中，因此$d[u]\leq d[y]$，因此必有$d[y]=\delta (s,y)=\delta (s,u)=d[u]$，也就证明了$u$点不可能不满足该条件，上述假设为假，原命题得证。

终止：终止时，$Q=\emptyset$，由于$Q=V-S$，因此$V=S$，因此对所有$u\in V$有$d[u]=\delta (s,u)$。

起源与历史

从鹿特丹到格罗宁根的最短路径是什么？实际上，这就是对于任意两座城市之间的最短路问题。解决这个问题实际上大概只花了我20分钟：一天早上，我和我的未婚妻在阿姆斯特丹购物，累了，我们便坐在咖啡馆的露台上喝咖啡，然后我就试了一下能否用一个算法解决最短路问题。正如我所说，这是一个20分钟的发现。不过实际上，我在3年后的1959年才把这个算法发表在论文上。即使现在来看这篇论文的可读性也非常高，这个算法之所以如此优雅，其中一个原因就是我没用笔纸就设计了它。后来我才知道，没用笔纸设计的优点之一是你不得不避免所有可避免的复杂问题。令我惊讶的是，这个算法最终成为我成名的基石之一。

——艾兹赫尔·戴克斯特拉在2001年的采访中提到戴克斯特拉算法的发现历程

戴克斯特拉1956年在荷兰数学和计算机科学研究学会担任程序员时为了展示新型计算机ARMAC的功能曾思考过最短路径问题的解法。他的目标是让不去实际计算的人也能理解这个问题和解决的方法，于是他在发现了这个算法之后在ARMAC上做了简单实验。1959年，他正式将此算法发表在期刊上，该算法也成为了戴克斯特拉成名的基石之一。

相关应用

一个多区域OSPF网络，在OSPF中使用本算法计算最短路径

链路状态路由协议中需要计算最短路时常常要用到该算法，该算法在开放最短路径优先和中间系统到中间系统协议中的相关应用是其在网络路由中的典型实现。

戴克斯特拉算法及其改进算法应用广泛，尤其是在寻路、交通、规划中。

如果有已知信息可用来估计某一点到目标点的距离，则可改用A*搜索算法，以减小最短路径的搜索范围，戴克斯特拉算法本身也可以看作是A*搜索算法的一个特例。

戴克斯特拉算法本身采用了与Prim算法类似的贪心策略。快速行进算法与戴克斯特拉算法同样有相似之处。

参考源程序

以下是该算法使用堆优化的一个C++实现参考：

// 無向圖
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

// iPair ==> Integer Pair（整数对）
typedef pair<int, int> iPair;

// 加边
void addEdge(vector<pair<int, int>> adj[], int u, int v, int wt)
{
    adj[u].push_back(make_pair(v, wt));
    adj[v].push_back(make_pair(u, wt));
}

// 计算最短路
void shortestPath(vector<pair<int, int>> adj[], int V, int src)
{
    // 关于stl中的优先队列如何实现，参考下方网址：
    // http://geeksquiz.com/implement-min-heap-using-stl/
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;

    // 距离置为正无穷大
    vector<int> dist(V, INF);
    vector<bool> visited(V, false);

    // 插入源点，距离为0
    pq.push(make_pair(0, src));
    dist[src] = 0;

    /* 循环直到优先队列为空 */
    while (!pq.empty())
    {
        // 每次从优先队列中取出顶点事实上是这一轮最短路径权值确定的点
        int u = pq.top().second;
        pq.pop();
        if (visited[u])
        {
            continue;
        }
        visited[u] = true;
        // 遍历所有边
        for (auto x : adj[u])
        {
            // 得到顶点边号以及边权
            int v = x.first;
            int weight = x.second;

            // 可以松弛
            if (dist[v] > dist[u] + weight)
            {
                // 松弛
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // 打印最短路
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}
int main()
{
    int V = 9;
    vector<iPair> adj[V];
    addEdge(adj, 0, 1, 4);
    addEdge(adj, 0, 7, 8);
    addEdge(adj, 1, 2, 8);
    addEdge(adj, 1, 7, 11);
    addEdge(adj, 2, 3, 7);
    addEdge(adj, 2, 8, 2);
    addEdge(adj, 2, 5, 4);
    addEdge(adj, 3, 4, 9);
    addEdge(adj, 3, 5, 14);
    addEdge(adj, 4, 5, 10);
    addEdge(adj, 5, 6, 2);
    addEdge(adj, 6, 7, 1);
    addEdge(adj, 6, 8, 6);
    addEdge(adj, 7, 8, 7);

    shortestPath(adj, V, 0);

    return 0;
}

以下是该算法Python的一个实现：

import sys
max = sys.maxsize

vertices_number = 6
adjacency_matrix = [
    [0, 1, 10, -1, -1, 2],
    [10, 0, 1, -1, -1, -1],
    [1, 10, 0, -1, -1, -1],
    [-1, -1, 2, 0, 1, 10],
    [-1, -1, -1, 10, 0, 1],
    [-1, -1, -1, 1, 10, 0]]
start = []
dest = ["2", "5"]
key = []


def init_keys(s: int):
    global key
    key = [ max ] * vertices_number
    key[s] = 0


def dijkstra(from_vertex, dest_vertex):
    fid = int(from_vertex) - 1
    tid = int(dest_vertex) - 1
    init_keys(fid)
    rel = [fid]
    min_vertex = fid
    hop_path = {}

    while len(rel) <= vertices_number and min_vertex != tid:
        for i in range(vertices_number):
            if i != min_vertex and i not in rel and \
                adjacency_matrix[min_vertex][i] > 0 \
                and key[i] > key[min_vertex] + adjacency_matrix[min_vertex][i]:
                key[i] = key[min_vertex] + adjacency_matrix[min_vertex][i]
                hop_path.update({i + 1: {"from": min_vertex + 1, "cost": adjacency_matrix[min_vertex][i]}})

        if min_vertex not in rel:
            rel.append(min_vertex)

        min_vertex = tid
        for i in range(vertices_number):
            if i not in rel and key[i] < key[min_vertex]:
                min_vertex = i

    if len(hop_path) == 0 or int(dest_vertex) not in hop_path:
        return -1, -1
    else:
        next_hop = int(dest_vertex)
        path_str = dest_vertex
        while hop_path[next_hop]["from"] != int(from_vertex):
            cost = hop_path[next_hop]["cost"]
            next_hop = hop_path[next_hop]["from"]
            path_str =  "{} -({})-> {}".format(str(next_hop), cost ,path_str)
        path_str =  "{} -({})-> {}".format(str(hop_path[next_hop]["from"]), hop_path[next_hop]["cost"], path_str)

        return key[tid], path_str



def find_shortest_router():
    for s in start:
        print("Forwarding Table for {}".format(s))
        print("{:>10} {:>10}       {}".format("To", "Cost", "Path"))
        for d in dest:
            c, n = dijkstra(s, d)
            print("{:>10} {:>10}       {}".format(d, c, n))


def main():
    for i in range(1, vertices_number + 1):
        if str(i) not in dest:
            start.append(str(i))
    find_shortest_router()

if __name__ == '__main__':
    main()

参见

• 图论
• A*搜索算法
• 贝尔曼-福特算法
• 宽度优先搜索
• Flood fill
• Floyd-Warshall算法
• 最长路径问题

参考

扩展阅读

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 24.3: Dijkstra's algorithm. Introduction to Algorithms second. MIT Press、S&P Global. 2001: 595–601. ISBN 0-262-03293-7. 
• Dial, Robert B. Algorithm 360: Shortest-path forest with topological ordering [H]. CACM. 1969, 12 (11): 632–633. doi:10.1145/363269.363610. 
• Zhan, F. Benjamin; Noon, Charles E. Shortest Path Algorithms: An Evaluation Using Real Road Networks. Transportation Science. February 1998, 32 (1): 65–73. doi:10.1287/trsc.32.1.65. 
• Knuth, D.E. A Generalization of Dijkstra's Algorithm. Information Processing Letters. 1977, 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3. 
• Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. Faster Algorithms for the Shortest Path Problem. Journal of Association for Computing Machinery (ACM). April 1990, 37 (2): 213–223. doi:10.1145/77600.77615. 
• Raman, Rajeev. Recent results on the single-source shortest paths problem. SIGACT News. 1997, 28 (2): 81–87. doi:10.1145/261342.261352. 
• Thorup, Mikkel. On RAM priority Queues. SIAM Journal on Computing. 2000, 30 (1): 86–109. doi:10.1137/S0097539795288246. 
• Thorup, Mikkel. Undirected single-source shortest paths with positive integer weights in linear time. journal of the ACM. 1999, 46 (3): 362–394 [2017-11-01]. doi:10.1145/316542.316548. （原始内容存档于2017-09-21）. 
• ZHANG Lin-guang,FANG Jin-yun,SHEN Pai-wei. An Improved Dijkstra Algorithm Based on Pairing Heap. Journal of Image and Graphics. 2007-05. 

外部链接

• 迪科斯彻算法分解演示视频（优酷） （页面存档备份，存于互联网档案馆）
• Animation of Dijkstra's algorithm （页面存档备份，存于互联网档案馆）
• The Boost Graph Library (BGL) （页面存档备份，存于互联网档案馆）
• Interactive Implementation of Dijkstra's Algorithm （页面存档备份，存于互联网档案馆）
• Shortest Path Problem: Dijkstra's Algorithm
• Dijkstra算法使用TDD的一个实现 （页面存档备份，存于互联网档案馆）
• Graphical explanation of Dijkstra's algorithm step-by-step on an example （页面存档备份，存于互联网档案馆）