戴克斯特拉算法
一种图搜索算法,用于寻找两点间的最短路 / 維基百科,自由的 encyclopedia
親愛的 Wikiwand AI, 讓我們通過簡單地回答這些關鍵問題來保持簡短:
你能列出最重要的事實和統計數據嗎 迪科斯彻算法?
為 10 歲的孩子總結這篇文章
顯示所有問題
戴克斯特拉算法(英語:Dijkstra's algorithm),又稱迪杰斯特拉算法、Dijkstra算法[6],是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表[7][8][9]。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图[9]的单源最短路径问题[10][1][2]。
事实速览 戴克斯特拉算法, 概况 ...
戴克斯特拉算法 | |
---|---|
戴克斯特拉算法运行演示(找到A,B之间的最短路),本算法每次取出未访问结点中距离最小的,用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。 | |
概况 | |
類別 | 搜索算法[1][2] 贪心算法[1] 动态规划[3] |
資料結構 | 图 堆/优先队列(算法优化)[1][4] |
复杂度 | |
最坏时间复杂度 | (使用斐波那契堆优化的戴克斯特拉算法)[5][4] |
空間複雜度 | (使用邻接表存储边的情况)[1] |
相关变量的定义 | |
代表图中边数,代表图中结点个数,为目前所有实际最短路径值不确定结点的集合,为目前所有实际最短路径值确定结点的集合,为到某点的最短路径估计,为到某点的最短路径实际值,为边集中边的最大权值。 |
关闭
该算法存在很多变体:戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径[9],后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径,产生一个最短路径树[1]。
该算法解决了圖 上带权的单源最短路径问题[1][11]:196–206。具体来说,戴克斯特拉算法设置了一顶点集合,在集合中所有的顶点与源点之间的最终最短路径权值均已确定[1]。算法反复选择最短路径估计最小的点并将加入中[1]。该算法常用于路由算法或者作为其他图算法的一个子模块[12]。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该演算法可以用来找到两个城市之间的最短路径[8][2]。
应当注意,绝大多数的戴克斯特拉算法不能有效处理带有负权边的图[1][13]。
戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索,并被认为是最良优先搜索(英语:best-first search)的一个特例[10]。