戴克斯特拉算法

来自testwiki
跳转到导航 跳转到搜索

Template:GA Template:NoteTA Template:Infobox algorithm Template:图搜索算法 戴克斯特拉算法（Template:Lang-en），又稱迪杰斯特拉算法、Dijkstra算法[1]，是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表[2][3][4]。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图Template:R的单源最短路径问题[5][6][7]。

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

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

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

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

描述

上圖為戴克斯特拉演算法應用示意圖。
起點以左下角的紅點，目標是右上角的綠點，中間灰色的倒L型為障礙物。藍色空圈表示"暫定"，用以搜索下一步；已經填充顏色的表示探訪過，圖中顏色以紅到綠，越綠表示離起點越遠。所有節點都被均勻探索。

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

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

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

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

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

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

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

-{}-
 1 procedure Dijkstra(G：边全为正权的图）
 2   {G带有顶点a=v0,v1,v2...和若干边w(vi,vj)}
 3    for i:=1 to n
 4       D(vi):=∞
 5    D(a):=0
 6    S:=∅
 7    while z∉S
 8    begin
 9          u:=不属于S的D(u)最小的一个顶点
 10        S:=S∪{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的最短路长度}

在该 算法演示页面 Template:Wayback，可以自定义节点，边的权重等信息，然后观察算法每一步的执行过程。

時間複雜度

我們可以用大O符號將该算法的運行時間表示為邊數|E|和頂點數|V|的函數[6]。

对于任何基于顶点集Q的实现，算法的运行时间是O(|E|⋅dkQ+|V|⋅emQ)，其中dkQ和emQ分别表示完成键的降序排列时间和从Q中提取最小键值的时间[6]。

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

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

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

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

算法 最坏时间复杂度  发现者（按照论文发表时间从前向后排序）
使用鄰接表的戴克斯特拉算法 O(|V|2) 莱索雷克及格雷等人[15]，艾兹赫尔·戴克斯特拉Template:R，明蒂[16]，怀廷及希利尔[17]
使用二叉堆优化的戴克斯特拉算法 O((|E|+|V|)log⁡|V|) 唐纳德·约翰逊[11]
使用斐波那契堆优化的戴克斯特拉算法 O(|E|+|V|log⁡|V|) 迈克尔·弗雷德曼及羅伯特·塔揚[13][12]
O(|E|log⁡log⁡|L|) 唐纳德·约翰逊[18]，洛夫·卡尔松及帕特里西奥·波夫莱特[19]

正确性证明

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

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

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

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

起源与历史

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

相关应用

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

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

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

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

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

参考源程序

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

// 無向圖
#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()

参见

Template:Portal

參考

参考文献

Template:Reflist

扩展阅读

Template:Refbegin

Template:Refend

外部連結

Template:Commons category

Template:算法

  1. ↑ Template:Cite journal
  2. ↑ Template:Cite web
  3. ↑ 3.0 3.1 3.2 3.3 Template:Cite journal
  4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Template:Cite journal
  5. ↑ 5.0 5.1 Template:Cite conference
  6. ↑ 6.00 6.01 6.02 6.03 6.04 6.05 6.06 6.07 6.08 6.09 6.10 6.11 6.12 6.13 6.14 6.15 6.16 6.17 6.18 6.19 6.20 6.21 6.22 6.23 6.24 6.25 引用错误：<ref>标签无效；未给name（名称）为IntroToAlgo的ref（参考）提供文本
  7. ↑ 7.0 7.1 7.2 7.3 7.4 7.5 7.6 7.7 Template:Cite book
  8. ↑ Template:Cite book
  9. ↑ 9.0 9.1 Template:Cite journal
  10. ↑ Template:Cite journal
  11. ↑ 11.0 11.1 11.2 Template:Cite journal
  12. ↑ 12.0 12.1 12.2 Template:Cite journal
  13. ↑ 13.0 13.1 引用错误：<ref>标签无效；未给name（名称）为tarjan的ref（参考）提供文本
  14. ↑ Template:Cite book
  15. ↑ Template:Cite book
  16. ↑ 见Template:Cite journal Attributes Dijkstra's algorithm to Minty ("private communication") on p.225.
  17. ↑ Template:Cite journal
  18. ↑ Template:Cite journal
  19. ↑ Template:Cite journal
  20. ↑ Template:Cite web
  21. ↑ Template:Cite journal
  22. ↑ Template:Cite journal
  23. ↑ Template:Cite journal
  24. ↑ Template:Cite journal
  25. ↑ Template:Citation.
  26. ↑ Template:Citation.
  27. ↑ Template:Citation
  28. ↑ Template:Cite journal
  29. ↑ 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)
  30. ↑ Template:Cite journal
  31. ↑ Template:Cite web
检索自“https://zh.wiki.beta.math.wmflabs.org/w/index.php?title=戴克斯特拉算法&oldid=2081”