戴克斯特拉演算法

$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$中。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該演演算法可以用來找到兩個城市之間的最短路徑。

應當注意，絕大多數的戴克斯特拉演算法不能有效處理帶有負權邊的圖。

戴克斯特拉演算法在電腦科學的人工智慧等領域也被稱為均一開銷搜索，並被認為是最良優先搜索的一個特例。

## 描述

<image>

戴克斯特拉演算法通過保留目前為止所找到的每個頂點$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)                //实际上的操作是将每个除原点外的顶点的<math>d[v]</math>置为无穷大，<math>d[s]=0</math>
 3   <math>S \leftarrow \emptyset</math>
 4   <math>Q \leftarrow s</math>                                //<math>Q</math>是顶点<math>V</math>的一个优先队列，以顶点的最短路径估计排序
 5   while(<math> Q \not= \emptyset</math>)
 6       do <math> u \leftarrow EXTRACT-MIN(Q)</math>          //选取<math>u</math>为<math>Q</math>中最短路径估计最小的顶点
 7       <math>S \leftarrow S \cup u</math>
 8       for each vertex v <math>\in Adj[u]</math>
 9            do RELAX(u, v, w)            //松弛成功的结点会被加入到队列中
```

如果我們只對在$s$和$t$之間尋找一條最短路徑的話，我們可以在第5或第6行添加條件如果滿足$u=t$的話終止程序。

在肯尼·羅森所著的《離散數學及其應用》中給出了如下的另一份偽代碼：

```
 1 '''procedure''' Dijkstra(G：边全为正权的图）
 2   {G带有顶点<math>a=v_0,v_1,v_2...</math>和若干边<math>w(v_i,v_j)</math>}
 3    for <math>i:=1</math> to n
 4       <math>D(v_i):=\infty</math>
 5    <math>D(a):=0</math>
 6    <math>S:=\emptyset</math>
 7    while <math>z \notin S</math>
 8    begin
 9         <math>u:=</math>不属于<math>S</math>的<math>D(u)</math>最小的一个顶点
 10        <math>S:=S \cup \{u\}</math>
 11        for 所有不属于<math>S</math>的顶点<math>v</math>
 12            if <math>D(u)+w(u,v)<D(v)</math> then <math>D(v):=D(u)+w(u,v)</math>
 13    end{<math>D(z)=</math>从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|)$｜唐納德·詹森，洛夫·卡爾松及帕特里西奧·波夫萊特

$O(|E|log^{2/3}|V|)$｜清華 段然團隊

## 正確性證明

<image>

戴克斯特拉本人在他的論文中給出了一份簡單的證明。

《演算法導論》使用循環不變式（數學歸納法）給出了如下的一份證明：

已知一帶權圖$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=\empty$，因此循環不變式顯然成立。

保持：實際上要證明每一輪循環中加入到$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=\empty$，由於$Q=V-S$，因此$V=S$，因此對所有$u \in V$有$d[u]=\delta(s,u)$。

## 起源與歷史

戴克斯特拉1956年在荷蘭數學和電腦科學研究學會擔任程式設計師時為了展示新型電腦ARMAC的功能曾思考過最短路徑問題的解法。他的目標是讓不去實際計算的人也能理解這個問題和解決的方法，於是他在發現了這個演算法之後在ARMAC上做了簡單實驗。1959年，他正式將此演算法發表在期刊上，該演算法也成為了戴克斯特拉成名的基石之一。

## 相關應用

<image>

鏈路狀態路由協議中需要計算最短路時常常要用到該演算法，該演算法在開放最短路徑優先和中間系統到中間系統協議中的相關應用是其在網路路由中的典型實現。

戴克斯特拉演算法及其改進演算法應用廣泛，尤其是在尋路、交通、規劃中。

如果有已知資訊可用來估計某一點到目標點的距離，則可改用A*搜尋演算法，以減小最短路徑的搜索範圍，戴克斯特拉演算法本身也可以看作是A*搜索算法的一個特例。

戴克斯特拉演算法本身採用了與Prim演算法類似的貪心策略。快速行進算法與戴克斯特拉演算法同樣有相似之處。

## 參考源程序

以下是該演算法使用堆優化的一個C++實現參考：

```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的一個實現：

```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()
```

## 外部連結

- 迪科斯徹演算法分解演示影片（優酷）
- 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

## 基本資料

- 車輛類別：搜索算法、貪心算法、動態規劃
- data：圖、堆/優先隊列（演算法優化）
- 時間：$O(|E| + |V| \log|V|)$（使用斐波那契堆優化的戴克斯特拉演算法）
- SpaceComp：$O(|E|+|V|)$（使用鄰接表存儲邊的情況）
- Def1：$|E|$代表圖中邊數，$|V|$代表圖中結點個數，$Q$為目前所有實際最短路徑值不確定結點的集合，$S$為目前所有實際最短路徑值確定結點的集合，$d[]$為到某點的最短路徑估計，$\delta$為到某點的最短路徑實際值，$|L|$為邊集中邊的最大權值。