戴克斯特拉算法

✍ dations ◷ 2024-12-26 22:07: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]}$

相关

富阳区富阳区是中国浙江省杭州市的市辖区，位于杭州市西南部，与西湖区、萧山区、余杭区、临安区和桐庐县接壤，距杭州市中心32公里，辖区总面积1831平方公里，户籍人口65.9万（常住人口71.7万
正蓝旗 (内蒙古)正蓝旗（蒙古语：.mw-parser-output .font-mong{font-family:"Menk Hawang Tig","Menk Qagan Tig","Menk Garqag Tig","Menk Har_a Tig","Menk Scnin Tig","Oyun Gurban Ulus Ti
陶菲克帕夏陶菲克帕夏（1852年11月15日－1892年1月7日），埃及穆罕默德·阿里王朝的第6任统治者，1879年至1892年间，成为埃及与苏丹的赫迪夫。陶菲克帕夏生于赫勒万，为伊斯梅尔帕夏的长子。1892年，
大帝汶大帝汶（印尼语：Timor Raya）是一个民族统一主义的概念，该思想主张一个独立与统一的帝汶岛，包括原先的葡属东帝汶与荷属西帝汶（现属于印度尼西亚）。1975年东帝汶被印尼占领后，印尼于19
阿拉斯阿拉斯（法语：Arras，法语发音：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gentium","Gen
丁承运丁承运（1944年－），河南开封人，中国泛川派古琴演奏家、斲琴师。国家级非物质文化遗产古琴艺术代表性传承人。妻子为武汉音乐学院作曲系副教授、古瑟家和作曲家傅丽娜。现为武汉音乐
布雷岛坐标：69°16′N 77°00′W / 69.267°N 77.000°W / 69.267; -77.000布雷岛是加拿大的岛屿，位于福克斯湾，属于北极群岛的一部分，由基瓦里奇地区负责管辖，长37公里、宽25公里，面积6
嘉理慰嘉理慰(Rev. John Galloway,1877年－1968年)，是美南浸信会牧师。由于杜心余牧师从澳门回到美国述职后不久患病身故，美南浸信会遂差派嘉理慰牧师接手其职务，并于1908年被抵达澳门，
杨宗震 (顺治三年进士)杨宗震（生卒年不详），字严四，山东济宁州人。清初官员。顺治二年，乡试中举。顺治三年（1646年）中式丙戌科三甲进士，此为清朝首次开科。官至江南驿盐道。
前389年