戴克斯特拉算法

✍ dations ◷ 2025-07-02 09:05:09 #戴克斯特拉算法

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

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

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

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

戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是最良优先搜索（英语：best-first search）的一个特例。

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

松弛操作是戴克斯特拉算法的基础操作：如果存在一条从 ${displaystyle u}$ $u$ 到 ${displaystyle v}$ $v$ 的边，那么从 ${displaystyle s}$ $s$ 到 ${displaystyle v}$ $v$ 的一条新路径是将边 ${displaystyle w(u,v)in E}$ ${displaystyle w(u,v)in E}$ 添加到从 ${displaystyle s}$ $s$ 到 ${displaystyle u}$ $u$ 的路径尾部来拓展一条从 ${displaystyle s}$ $s$ 到 ${displaystyle v}$ $v$ 的路径。这条路径的长度是 ${displaystyle d+w(u,v)}$ ${displaystyle d+w(u,v)}$ 。如果这个值比目前已知的 ${displaystyle d}$ ${displaystyle d}$ 的值要小，那么可以用这个值来替代当前 ${displaystyle d}$ ${displaystyle d}$ 中的值。松弛边的操作一直执行到所有的 ${displaystyle d}$ ${displaystyle d}$ 都代表从 ${displaystyle s}$ $s$ 到 ${displaystyle v}$ $v$ 的最短路径的长度值。

算法维护两个顶点集合 ${displaystyle S}$ $S$ 和 ${displaystyle Q}$ $Q$ 。集合 ${displaystyle S}$ $S$ 保留所有已知实际最短路径值的顶点，而集合 ${displaystyle Q}$ $Q$ 则保留其他所有顶点。集合 ${displaystyle S}$ $S$ 初始状态为空，而后每一步都有一个顶点从 ${displaystyle Q}$ $Q$ 移动到 ${displaystyle S}$ $S$ 。这个被选择的顶点是 ${displaystyle Q}$ $Q$ 中拥有最小的 ${displaystyle d}$ ${displaystyle d}$ 值的顶点。当一个顶点 ${displaystyle u}$ $u$ 从 ${displaystyle Q}$ $Q$ 中转移到了 ${displaystyle S}$ $S$ 中，算法对 ${displaystyle u}$ $u$ 的每条外接边 ${displaystyle w(u,v)}$ ${displaystyle w(u,v)}$ 进行松弛。

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

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

如果我们只对在 ${displaystyle s}$ $s$ 和 ${displaystyle t}$ $t$ 之间查找一条最短路径的话，我们可以在第5或第6行添加条件如果满足 ${displaystyle u=t}$ ${displaystyle u=t}$ 的话终止程序。

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

 1 procedure Dijkstra(G：边全为正权的图） 2   {G带有顶点 ${displaystyle a=v_{0},v_{1},v_{2}...}$  ${displaystyle a=v_{0},v_{1},v_{2}...}$ 和若干边 ${displaystyle w(v_{i},v_{j})}$  ${displaystyle w(v_{i},v_{j})}$ } 3    for  ${displaystyle i:=1}$  ${displaystyle i:=1}$  to n 4        ${displaystyle D(v_{i}):=infty }$  ${displaystyle D(v_{i}):=infty }$  5     ${displaystyle D(a):=0}$  ${displaystyle D(a):=0}$  6     ${displaystyle S:=emptyset }$  ${displaystyle S:=emptyset }$  7    while  ${displaystyle znotin S}$  ${displaystyle znotin S}$  8    begin 9           ${displaystyle u:=}$  ${displaystyle u:=}$ 不属于 ${displaystyle S}$  $S$ 的 ${displaystyle D(u)}$  ${displaystyle D(u)}$ 最小的一个顶点 10         ${displaystyle S:=Scup {u}}$  ${displaystyle S:=Scup {u}}$  11        for 所有不属于 ${displaystyle S}$  $S$ 的顶点 ${displaystyle v}$  $v$  12            if  ${displaystyle D(u)+w(u,v)<D(v)}$  ${displaystyle D(u)+w(u,v)<D(v)}$  then  ${displaystyle D(v):=D(u)+w(u,v)}$  ${displaystyle D(v):=D(u)+w(u,v)}$  13    end{ ${displaystyle D(z)=}$  ${displaystyle D(z)=}$ 从a到z的最短路长度}

时间复杂度

我们可以用大O符号将该算法的运行时间表示为边数 ${displaystyle |E|}$ $|E|$ 和顶点数 ${displaystyle |V|}$ $|V|$ 的函数。

对于任何基于顶点集 ${displaystyle Q}$ $Q$ 的实现，算法的运行时间是 ${displaystyle O(|E|cdot dk_{Q}+|V|cdot em_{Q})}$ $O(|E|cdot dk_{Q}+|V|cdot em_{Q})$ ，其中 ${displaystyle dk_{Q}}$ $dk_{Q}$ 和 ${displaystyle em_{Q}}$ $em_{Q}$ 分别表示完成键的降序排列时间和从 ${displaystyle Q}$ $Q$ 中提取最小键值的时间。

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

对于边数少于 ${displaystyle |V|^{2}}$ ${displaystyle |V|^{2}}$ 的稀疏图来说，可以用邻接表来更有效的实现该算法。

可以使用一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点（ ${displaystyle Extract-Min}$ ${displaystyle Extract-Min}$ ）以优化算法。当用到二叉堆的时候，算法所需的时间为 ${displaystyle O((|E|+|V|)log |V|)}$ ${displaystyle O((|E|+|V|)log |V|)}$ ，斐波纳契堆能提高一些性能，让算法运行时间达到 ${displaystyle O(|E|+|V|log |V|)}$ $\text{[math]}$

相关

养成过程人体解剖学 - 人体生理学组织学 - 胚胎学人体寄生虫学 - 免疫学病理学 - 病理生理学细胞学 - 营养学流行病学 - 药理学 - 毒理学医生又称医师，在中国古代称大夫或郎中
澳大利亚大陆澳大拉西亚（拉丁语：Australasia）一般指大洋洲的一个地区，如澳大利亚、新西兰和邻近的太平洋岛屿。澳大拉西亚（Australasia）一词是由法国学者布罗塞（法语：Charles de Brosses）于1756年
华容县华容县是湖南省岳阳市西部的县，位于洞庭湖北部。地图坐标为东经112°8'31"～113°1'32"，北纬29°10'18"～29°48'27"之间。GDP总量216.54亿元（2012年）。传统农业为水稻种植，家庭养殖
民族语言民族语言，或译为国语（英语：national language），一般简称族语，通常是指在事实上（）或在法律上（），能代表一个地区人民的的语言。在民族国家，此民族语言通常亦是官方语言。官方语言通常是由
绿洲曳影《绿洲曳影》（오아시스）又译作《情欲绿洲》是一部韩国电影，由韩国导演李沧东编剧及导演，2002年上映。《绿洲曳影》于第59届威尼斯影展首映。刑满释放的洪忠都出狱后，家人对他横
三须宗太郎三须宗太郎（日语：三須宗太郎／みすそうたろう ?），大日本帝国海军军人，1855年9月16日（安政元年11月3日）出生于近江国彦根藩， 1921年（大正10年）12月24日去世。最终军阶为海军大将。受
卡肯果卡肯果（）是一类已灭绝的银杏类植物，包括卡肯果科（Karkeniaceae）。卡肯果科下仅有一属，即卡肯果属（）。发现于早侏罗世到早白垩世地层。卡肯果的胚珠小而多，生长在短枝上。胚珠向内弯转
牛顿书信牛顿书信(The Newton Letter)是约翰·班维尔于1982年写成的小说, 讲述一个年老且不具名的历史学家为了尽早完成他关于牛顿的传记书，走到一个爱尔兰的乡间的“蕨之屋”。他在
算法少女算法少女是一本出版于1775年（安永4年）的和算书籍。本书是日本传统算学书籍中唯一一本以女性名义编写的。本书在日本国立国会图书馆有扫描本公开。在1935年曾由古典数学书院发
新裤子新裤子乐队（NEW PANTS）是一支中国的摇滚乐队，成立于1996年，是属于摩登天空旗下的组合。曾获得2003年的CCTV-MTV音乐盛典的“内地年度新锐乐队”。目前该乐队由主唱兼吉他手彭磊、键盘手庞宽、贝斯手赵梦、鼓手Hayato（日籍，原名：木藤隼人）组成。新裤子是代表中国新浪潮音乐的标志性乐队之一。新裤子乐队在最初组建时共有三人，分别是主唱彭磊、贝斯刘葆和鼓手尚笑，他们在高中时期（1995年）结识，组建了乐队“金属车间的形体师傅”。由彭磊担任主唱兼吉他手，刘葆担任贝司手，尚笑担任鼓手。与摩登天空签