跳转到内容

戴克斯特拉算法

这是一篇优良条目,点击此处获取更多信息。
本页使用了标题或全文手工转换
维基百科,自由的百科全书

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

戴克斯特拉算法(英语:Dijkstra's algorithm),又称迪杰斯特拉算法Dijkstra算法[6],是由荷兰电脑科学家艾兹赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表[7][8][9]。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图[9]的单源最短路径问题[10][1][2]

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

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

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

戴克斯特拉算法在电脑科学的人工智慧等领域也被称为均一开销搜索,并被认为是最良优先搜索英语best-first search的一个特例[10]

描述

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

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

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

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

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

 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][2]

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

 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符号将该算法的运行时间表示为边数和顶点数的函数[1]

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

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

对于边数少于的稀疏图来说,可以用邻接表来更有效的实现该算法[1]

可以使用一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点()以优化算法[14][15]。当用到二叉堆的时候,算法所需的时间为[14]斐波纳契堆能提高一些性能,让算法运行时间达到[4][15]。然而,使用斐波纳契堆进行编程,有时会由于算法常数过大而导致速度没有显著提高[16]

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

算法 最坏时间复杂度  发现者(按照论文发表时间从前向后排序)
使用邻接表的戴克斯特拉算法 莱索雷克及格雷等人[17]艾兹赫尔·戴克斯特拉[9],明蒂[18],怀廷及希利尔[19]
使用二叉堆优化的戴克斯特拉算法 唐纳德·约翰逊[14]
使用斐波那契堆优化的戴克斯特拉算法 迈克尔·弗雷德曼及罗伯特·塔扬[4][15]
唐纳德·约翰逊[20],洛夫·卡尔松及帕特里西奥·波夫莱特[21]

正确性证明

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

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

算法导论》使用循环不变式(数学归纳法)给出了如下的一份证明[1]

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

起源与历史

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

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

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

相关应用

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

链路状态路由协议英语Link-state routing protocol中需要计算最短路时常常要用到该算法,该算法在开放最短路径优先中间系统到中间系统协议中的相关应用是其在网络路由中的典型实现[12]

戴克斯特拉算法及其改进算法应用广泛,尤其是在寻路交通规划[23][24][25][26]

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

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

参考源程序

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

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

参见

参考

参考文献

  1. ^ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 24.3: Dijkstra's algorithm. Introduction to Algorithms Second. MIT Press and McGraw–Hill. 2001: 595–601. ISBN 0-262-03293-7. 
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill College. 2002. ISBN 0-07-293033-0. 
  3. ^ 有争议,见:Moshe Sniedovich. Dijkstra's algorithm revisited: the dynamic programming connexion. Control and Cybernetics. 2006, 35: 599–620 [2020-03-04]. (原始内容存档于2020-03-04). 
  4. ^ 4.0 4.1 4.2 4.3 Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE: 338–346. 1984. doi:10.1109/SFCS.1984.715934. 
  5. ^ Andrew V. Goldberg; Robert E. Tarjan. Expected performance of Dijkstra’s shortest path algorithm. NEC Research Institute Report. 1996年 [2019-12-12]. (原始内容存档于2021-11-22). 
  6. ^ 乐阳、龚健雅. Dijkstra最短路径算法的一种高效率实现. 《科学技术创新》. 2020, (17): 75–77 [2020-06-30]. (原始内容存档于2021-02-13). 
  7. ^ Richards, Hamilton. Edsger Wybe Dijkstra. A.M. Turing Award. Association for Computing Machinery. [2017-10-16]. (原始内容存档于2017-10-21). At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities? 
  8. ^ 8.0 8.1 8.2 8.3 8.4 Frana, Phil. An Interview with Edsger W. Dijkstra. Communications of the ACM. August 2010, 53 (8): 41–47. doi:10.1145/1787234.1787249. 
  9. ^ 9.00 9.01 9.02 9.03 9.04 9.05 9.06 9.07 9.08 9.09 9.10 Dijkstra, E. W. A note on two problems in connexion with graphs (PDF). Numerische Mathematik. 1959, 1: 269–271 [2020-01-27]. doi:10.1007/BF01386390. (原始内容存档 (PDF)于2020-01-23). 
  10. ^ 10.0 10.1 Felner, Ariel. Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm. Proc. 4th Int'l Symp. on Combinatorial Search. 2011 [2020-02-18]. (原始内容存档于2020-02-18). 
  11. ^ Mehlhorn, Kurt; Sanders, Peter. Chapter 10. Shortest Paths (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. 2008 [2020-02-14]. ISBN 978-3-540-77977-3. doi:10.1007/978-3-540-77978-0. (原始内容存档 (PDF)于2021-02-24). 
  12. ^ 12.0 12.1 H. Ishikawa, S. Shimizu, Y. Arakawa, N. Yamanaka, K. Shiba. New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2. IEEE. 13 August 2007 [2020-03-21]. doi:10.1109/ICC.2007.332. (原始内容存档于2020-12-18). 
  13. ^ Yefim, Dinitz; Rotem, Itzhak. Hybrid Bellman–Ford–Dijkstra algorithm,. Journal of Discrete Algorithms. 2017, 42: 35–44. doi:10.1016/j.jda.2017.01.001. 
  14. ^ 14.0 14.1 14.2 Johnson, Donald B. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM. 1977, 24 (1): 1–13. doi:10.1145/321992.321993. 
  15. ^ 15.0 15.1 15.2 Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the Association for Computing Machinery. 1987, 34 (3): 596–615 [2018-04-03]. doi:10.1145/28869.28874. (原始内容存档于2006-04-28). 
  16. ^ Skiena, Steven. The Algorithm Design Manual (PDF) 2. Springer. 2008-07-26: 212 [2015-04-11]. ISBN 978-0073523408. doi:10.1007/978-1-84800-070-4. (原始内容 (PDF)存档于2015-06-09) (英语). 
  17. ^ Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology. 1957. 
  18. ^ Pollack, Maurice; Wiebenson, Walter. Solution of the Shortest-Route Problem—A Review. Oper. Res. March–April 1960, 8 (2): 224–230. doi:10.1287/opre.8.2.224.  Attributes Dijkstra's algorithm to Minty ("private communication") on p.225.
  19. ^ Whiting, P. D.; Hillier, J. A. A Method for Finding the Shortest Route through a Road Network. Operational Research Quarterly. March–June 1960, 11 (1/2): 37–40. doi:10.1057/jors.1960.32. 
  20. ^ Johnson, Donald B. A priority queue in which initialization and queue operations take O(log log D) time. Mathematical Systems Theory. December 1981, 15 (1): 295–309. MR 0683047. doi:10.1007/BF01786986. 
  21. ^ Karlsson, Rolf G.; Poblete, Patricio V. An O(m log log D) algorithm for shortest paths. Discrete Applied Mathematics. 1983, 6 (1): 91–93. MR 0700028. doi:10.1016/0166-218X(83)90104-X. 
  22. ^ ARMAC. Unsung Heroes in Dutch Computing History. 2007. (原始内容存档于2013-11-13). 
  23. ^ Sven Peyer; Dieter Rautenbach,Jens Vygen. A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing. Journal of Discrete Algorithms. 2007, 7 (4): 377–390. doi:10.1016/j.jda.2007.08.003. 
  24. ^ Ismail Rakip Karas,Sait Demir. Dijkstra algorithm interactive training software development for network analysis applications in GIS (PDF). Energy Education Science and Technology Part A: Energy Science and Research. 2011, 28: 445–452 [2020-03-04]. (原始内容存档 (PDF)于2020-03-04). 
  25. ^ Dean Djokic,David R. Maidment. Application of GIS Network Routines for Water Flow and Transport. Journal of Water Resources Planning and Management. 1993, 119 (2). doi:10.1061/(ASCE)0733-9496(1993)119:2(229). 
  26. ^ 江琦浩. 迪杰斯特拉算法在企业成本控制研究中的应用. 中国商贸. 2012, (03X) [2020-12-24]. (原始内容存档于2021-02-13). 
  27. ^ De Smith, Michael John; Goodchild, Michael F.; Longley, Paul, Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools, Troubadour Publishing Ltd: 344, 2007 [2020-03-04], ISBN 9781905886609, (原始内容存档于2017-02-27) .
  28. ^ Hetland, Magnus Lie, Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress: 214, 2010 [2020-03-04], ISBN 9781430232377, (原始内容存档于2017-02-28) .
  29. ^ Tarjan, Robert Endre, Data Structures and Network Algorithms, CBMS_NSF Regional Conference Series in Applied Mathematics 44, Society for Industrial and Applied Mathematics: 75, 1983, The third classical minimum spanning tree algorithm was discovered by Jarník and rediscovered by Prim and Dikstra; it is commonly known as Prim's algorithm. 
  30. ^ Prim, R.C. Shortest connection networks and some generalizations (PDF). Bell System Technical Journal. 1957, 36 (6): 1389–1401 [18 July 2017]. Bibcode:1957BSTJ...36.1389P. doi:10.1002/j.1538-7305.1957.tb01515.x. (原始内容 (PDF)存档于18 July 2017). 
  31. ^ 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)
  32. ^ Danielsson, Per-Erik; Lin, Qingfen. A Modified Fast Marching Method. Image Analysis. 24 June 2003: 1154–1161 [2020-03-25]. (原始内容存档于2021-02-13). 
  33. ^ geeksforgeeks. Dijkstra’s Shortest Path Algorithm using priority_queue of STL. geeksforgeeks. [2020-05-11]. (原始内容存档于2021-02-13). 

扩展阅读

外部链接