戴克斯特拉算法

✍ dations ◷ 2025-08-10 16:53:32 #戴克斯特拉算法

戴克斯特拉算法（英语：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]}$

相关

LGBT刻板印象LGBT刻板印象是指社会对于LGBT人群的公式化的概括、观点或印象。消极的LGBT刻板印象经常和同性恋恐惧症有关，但也存在积极的LGBT刻板印象。传统的对男同性恋的刻板印象包括女
艾沙格·贾汉基里埃沙格·贾汉吉里（波斯语：اسحاق جهانگیری کوهشاهی‎；1958年1月21日－），伊朗政治家。贾汉吉里曾担任过两任伊斯兰议会议员，后任伊斯法罕省省长，再后于1997年至200
亲爱的姊妹《亲密姐妹》（日语：ディア♥シスター，英语：），为日本富士电视台从2014年10月16日开始于周四剧场（JST 22:00 - 22:54）播出的连续剧，由石原聪美、松下奈绪主演。天真烂漫、自由奔放的27
氘燃烧氘燃烧是发生在一些恒星和次恒星天体的核聚变反应，其中的氘原子核和质子相结合，形成一个氦-3核聚变反应。它发生在质子-质子链反应的第二阶段，由两个质子融合形成一个氘原子核，
爱德华·吉布森爱德华·乔治·吉布森博士（Edward George Gibson, PhD，1936年11月8日－）曾是一位美国国家航空航天局的宇航员，执行过天空实验室4号任务。
牛角瓜牛角瓜（学名：，英文名称：），别称断肠草（广东）、五狗卧花（广东崖县）、羊浸树（云南、广东）、羊浸渣叶、哮喘树、大麻风药、奶浆包、皇冠花、紫冠花、五狗卧花心、野攀枝花及牛角瓜叶等，为夹竹
顾复生顾复生（1900年11月－1995年2月），男，江苏青浦（今属上海）人，中国军事人物、政治人物，曾任江苏省农业科学院院长，江苏省政协副主席。
高洋 (演员)高洋（1985年1月23日－），出生于辽宁省营口市，是一位中国大陆新生代演员。出道初期与林申、杨洋、于小彤、徐海乔、蒋梦婕、李沁、阚清子、李依蔓、马晓灿为荣信达影视力捧演员。高
Surface HubSurface Hub是一个微软产品，Microsoft Surface家族的一部分。微软在Windows 10发布时，一并公布于2015年1月21日。Surface Hub采用了长宽比16:9的84吋及55吋屏幕，可使用Surface Hub Pens或手指触控操作画面。主要功能是为企业自2015年7月1日起进行订购业务。但是，航运辅助功能从9月1日推迟，直到2016年第一季度才可使用。Surface Hub 可使用配件装设在墙壁或滚轮架。按大小配有两套规格，84英寸设备(120赫兹)的高配版和55英
青春之旅《青春之旅》（日语：アオハライド）是日本漫画家咲坂伊绪的日本漫画作品。于《别册Margaret》（集英社）连载。2014年7月开始播放电视动画。同年12月真人电影上映。吉冈双叶从中学时期就很不擅长和男生相处，却有一位名为“田中”的男生例外，然而田中在暑假转学了，双叶也来不及传达自己的心意。之后，在男生群非常受欢迎的双叶遭受女生的排挤，在升上高中后的双叶为了不再让女生讨厌决定要伪装自己，同时她与中学时代的初恋的“田中”再次相遇了……2014年7月至9月，分别于东京都会电视台（TOKYO MX）、MBS 电视