戴克斯特拉算法

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

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

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

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

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

 描述 
戴克斯特拉算法通過保留目前為止所找到的每個頂點從到的最短路徑來工作。初始時，原點的路径权重被賦為 0 （即原点的实际最短路径=0）。同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑。當算法結束時， 中儲存的便是從到的最短路徑，或者如果路徑不存在的話是無窮大。

松弛操作是戴克斯特拉算法的基礎操作：如果存在一條從到的邊，那麼從到的一条新路径是將邊添加到從到的路徑尾部來拓展一條從到的路径。這條路徑的長度是。如果這個值比目前已知的的值要小，那么可以用这个值來替代當前中的值。松弛邊的操作一直執行到所有的都代表從到的最短路徑的长度值。

算法維護兩個頂點集合和。集合保留所有已知实际最短路径值的頂點，而集合則保留其他所有頂點。集合初始狀態為空，而後每一步都有一個頂點從移動到。這個被選擇的頂點是中擁有最小的值的頂點。當一個頂點從中轉移到了中，算法對的每条外接邊進行松弛。

《算法导论》中给出了以下伪代码：该伪代码计算并保留图中原点到每一顶点的最短距离。其中，函数将頂點集合中有最小值的頂點从中删除并返回。

 -{}-
  1  function Dijkstra(G, w, s)
  2   INITIALIZE-SINGLE-SOURCE(G, s)                //实际上的操作是将每个除原点外的顶点的置为无穷大，
  3   
  4                                   //是顶点的一个优先队列，以顶点的最短路径估计排序
  5   while()
  6       do           //选取为中最短路径估计最小的顶点
  7       
  8       for each vertex v 
  9            do RELAX(u, v, w)            //松弛成功的结点会被加入到队列中

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

在肯尼·罗森所著的《离散数学及其应用》中给出了如下的另一份伪代码：
 -{}-
  1 procedure Dijkstra(G：边全为正权的图）
  2   {G带有顶点和若干边}
  3    for  to n
  4       
  5    
  6    
  7    while 
  8    begin
  9          不属于的最小的一个顶点
  10        
  11        for 所有不属于的顶点
  12            if  then 
  13    end{从a到z的最短路长度}

 時間複雜度 
我們可以用大O符號將该算法的運行時間表示為邊數和頂點數的函數。

对于任何基于顶点集的实现，算法的运行时间是，其中和分别表示完成键的降序排列时间和从中提取最小键值的时间。

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

對於邊數少於的稀疏圖來說，可以用鄰接表來更有效的實現该算法。

可以使用一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點（）以优化算法。當用到二叉堆的時候，算法所需的時間為，斐波納契堆能提高一些性能，讓算法運行時間達到。然而，使用斐波納契堆进行编程，有时会由于算法常数过大而导致速度没有显著提高。

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

 算法  最坏时间复杂度  发现者（按照论文发表时间从前向后排序） 使用鄰接表的戴克斯特拉算法   莱索雷克及格雷等人，艾兹赫尔·戴克斯特拉，明蒂见  Attributes Dijkstra's algorithm to Minty ("private communication") on p.225.，怀廷及希利尔 使用二叉堆优化的戴克斯特拉算法   唐纳德·约翰逊使用斐波那契堆优化的戴克斯特拉算法  迈克尔·弗雷德曼及羅伯特·塔揚    唐纳德·约翰逊，洛夫·卡尔松及帕特里西奥·波夫莱特清华段然团队

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

《算法导论》使用循环不变式（数学归纳法）给出了如下的一份证明：
已知一带权图，其加权函数的值非负，源点为。对该图运行戴克斯特拉算法，对所有有。其中表示u点的最短路径估计，表示到点的最短路径。
证明：证明如下的循环不变式成立即可：在每次执行EXTRACT-MIN时，对每个顶点，有成立即可。由于上界性质，在加入了之后，一旦有，则在后面的每次循环中都不会改变这个性质。
初始化：第一次循环前，，因此循环不变式显然成立。
保持：实际上要证明每一轮循环中加入到中的结点满足。利用反证法，假设是第一个不满足此条件的结点，考虑循环开始前的状况，首先一定不等于，这是显然的。其次一定有到的路径，否则路径为无穷大。那么假设在进入时，有最短路径，假设该路径上存在两个点，。、，且x是y的前驱，路径可以分解为（此处表示经过这条路径，后同），其中路径和路径可以为空。由于是第一个不满足的，又因为是满足该条件的，而且一定已经被松弛过了，所以是满足该条件的。
现在只需要推出矛盾，即可证明u不存在：在之前出现，而且图中所有权值非负，因此有，所以：，但是由于和同时在中，因此，因此必有，也就证明了点不可能不满足该条件，上述假设为假，原命题得证。
终止：终止时，，由于，因此，因此对所有有。

起源与历史

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

 相关应用

链路状态路由协议中需要计算最短路时常常要用到该算法，该算法在開放最短路徑優先和中间系统到中间系统协议中的相关应用是其在網絡路由中的典型實現。

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

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

戴克斯特拉算法本身采用了与Prim算法类似的贪心策略V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)。快速行进算法与戴克斯特拉算法同样有相似之处。

 参考源程序                                                                                                                                    
以下是该算法使用堆优化的一个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算法
 最长路径问题

 參考 
参考文献

扩展阅读







 外部連結 

 迪科斯彻算法分解演示视频（优酷） 
 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 

Category:艾兹赫尔·戴克斯特拉
Category:图算法
Category:搜尋演算法
Category:组合优化
Category:带有伪代码示例的条目
D
D