戴克斯特拉算法

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

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

相关

1类致癌物对人类有确认的致癌性的物质、混合物和接触场合被国际癌症研究机构列为1类致癌物。这里的有些物质尽管没有特别充分的致癌性证据，但有足够的证据证明它们对动物致癌，而且能从
氖燃烧过程氖燃烧过程是大质量恒星（至少8MSun）内进行的核聚变反应，因为氖燃烧需要高温和高密度（大约1.2×109 K和4×109千克/米3）在如此的高温下，光致蜕变成为很重要的作用，有一些氖核会分解，
比佛利山比弗利山（英语：Beverly Hills），又译作贝弗利希尔斯；译作比佛利山；港澳译作比华利山，是一座位于美国加州洛杉矶县西边的城市。比弗利山和邻近的西好莱坞被洛杉矶市完全包围。这个区
生物技术学生物技术（英语：biotechnology），又称为生物科技，指利用生物体（含动物，植物及微生物的细胞）来生产有用的物质或改进制程，改良生物的特性，以降低成本及创新物种的科学技术。根据不同的工
菲因岛菲英岛（丹麦语：Fyn，pronounced ）是丹麦仅次于西兰岛和北日德兰岛的第三大岛（若考虑丹麦的自治领地格陵兰则为第四大岛），是世界第165大岛，面积为2,984平方公里，主要城市为欧登塞，全岛
纽约及新泽西纽约及新泽西战役（英语：New York and New Jersey campaign），是指美国独立战争于1776年7月至1777年3月期间，美国与英国在纽约州及新泽西州的多场战斗。1776年3月波士顿战役结束后，
皮娜·鲍什皮娜·鲍什（德语：Pina Bausch，1940年7月27日－2009年6月30日），全名Philippine "Pina" Bausch，出生于德国索林根，现代舞编舞者。她在舞蹈风格中著名的德国舞蹈剧场（德语：Tanztheater）发展
施拉达·卡普尔施拉达·卡普尔（印度语：श्रद्धा कपूर，英语：英语：Shraddha Kapoor，1992年3月3日－）是印度宝莱坞女演员。卡普尔的父亲Shakti Kapoor是一名拥有旁遮普血统演员，母亲则是马拉
乌斯钵谷坐标：29°48′S 37°06′W / 29.8°S 37.1°W / -29.8; -37.1 (乌斯钵谷（Uzboi Vallis）)乌斯钵谷（Uzboi Vallis）是一个位于火星珍珠湾区的峡谷。该峡谷以土库曼斯坦的乌斯钵河命
塞尔哈特·巴尔哲塞尔哈特·巴尔哲（土耳其语：Serhat Balcı，1982年3月15日－），土耳其男子摔跤运动员。他曾代表土耳其参加世界摔跤锦标赛，获得一枚银牌和一枚铜牌。他也曾参加2008年和2012年夏季奥林匹克运动会。