戴克斯特拉算法是一种算法,用于求解边权非负的图中的单源最短路径问题。它从指定的源顶点出发,确定到达每个可达顶点所需的最小总权重;也可以在到达某个特定目标顶点、且已证明所得距离最优时提前终止。该算法的核心操作是:选出暂定距离最小、尚未定案的顶点,并将其距离确定为最终值。
该算法由艾兹赫尔·W. 戴克斯特拉提出,于1959年发表,此后成为计算机科学、网络优化和路线规划中的基础方法。它的正确性论证简明,且有多种实现方式,能够利用不同的图结构和权重取值范围。其实际运行表现很大程度上取决于图的表示方式,以及用于选取下一个顶点的机制。
该算法适用于距离、行程时间、通信成本以及其他可累加的量,前提是延长路径不会使其累计成本降低。这一条件既解释了它为何应用广泛,也揭示了它的主要局限:对于含有任意负边权的图,标准算法不能保证结果正确。
历史起源与数学背景
艾兹赫尔·W. 迪杰斯特拉于1956年在阿姆斯特丹数学中心工作期间设计了这一算法。他的论文《关于图的两个问题的注记》(A Note on Two Problems in Connexion with Graphs)于1959年发表于《数值数学》(Numerische Mathematik)第1卷,第269–271页。这篇论文同时讨论了最短路径问题和总长度最小的连接问题。其简洁的表述帮助确立了一种经久不衰的算法设计风格:维护一组定义清晰的局部结果,并通过具有局部合理性的选择逐步扩展这些结果。
这一算法的数学背景来自图论。图记作 ,其中顶点集为 ,边集为 ,权重函数为 。在有向图中,边 允许从 移动到 ,但不一定允许反向移动。无向边允许双向移动,在计算机中可以用两个有向的邻接项来表示。权重不一定是几何距离,也可以表示通行费、延迟、能耗,或任何适合累加的代价。
对于源顶点 ,所要求的到顶点 的距离为
如果不存在路径,则将距离定义为 。空路径给出 。由于所有权重均非负,从一条游走中去掉一个环不会增加其代价。因此,只要存在一条到达某个可达终点的最小代价游走,就也存在一条到达该终点的简单最短路径。零权重环可能产生更多最优游走,但不会改变最小距离。
算法通常输出一个距离数组,还可以选择输出前驱信息,凭借这些信息能够重建到每个可达顶点的一条最短路径。这是两类不同的输出:仅仅知道某个终点距离源点17个单位,并不能确定路线经过哪些边。最优路线可能不止一条,因此,即使各个距离都唯一确定,最短路径树也未必唯一。
该方法属于贪心算法,因为每轮迭代都会作出一个不可撤销的局部选择。它选择的既不是全图中代价最小的边,也不是从最近访问的顶点出发的代价最小的边,而是从源点出发的暂定总距离最小的顶点。这一区别将迪杰斯特拉算法与若干表面上相似的方法区分开来,也是其正确性证明的关键。
暂定距离、松弛与执行过程
算法为每个顶点维护一个暂定距离 。初始时,,其余所有距离均为 。前驱字段 初始时未定义。当算法确认某个顶点的暂定距离等于其实际最短路径距离时,就称该顶点为已确定顶点。已发现但尚未确定的顶点构成当前的搜索前沿。
算法的基本更新操作是松弛。检查一条边 时,算法将当前估计值 与经由 到达 的代价进行比较。如果
则赋值 ,并记录 。因此,松弛操作会用一条代价严格更低的路径替换已有路径。但这并不意味着新的估计值已经是最终值。
算法使用优先队列,按暂定距离组织搜索前沿。以下伪代码使用带索引的队列,其中每个入队顶点只有一个条目,且其优先级可以降低:
for each vertex v:
d[v] = infinity
predecessor[v] = undefined
settled[v] = false
d[source] = 0
Q.insert(source, 0)
while Q is not empty:
u = Q.extract_min()
settled[u] = true
for each edge (u, v) with weight w:
if settled[v]:
continue
candidate = d[u] + w
if candidate < d[v]:
d[v] = candidate
predecessor[v] = u
if Q contains v:
Q.decrease_key(v, candidate)
else:
Q.insert(v, candidate)
只有已发现的顶点才会进入这个队列。另一种做法是在初始化时将所有顶点放入队列,包括距离为无穷大的顶点;这种版本可以在队列中的最小键值为无穷大时停止。两个版本算出的有限距离相同,但在处理非连通图时,内存用量和计算工作量可能有所不同。
如果只查询一个目标顶点 ,那么一旦 以其当前最小键值从队列中取出并被确定,就可以停止执行。在首次发现 时就停止是不正确的:最先到达它的路径之后仍可能得到改进。对于限定距离的搜索,当尚未确定的最小距离超过允许的半径时,就可以停止执行。非负边权保证后续不会再有顶点落在该半径范围内。
目标顶点一旦被确定,就可以沿前驱指针反向追溯到源点,再将所得序列反转,从而重建路径。此操作所需的时间与返回路径中的边数成正比。提前停止后,尚未确定的顶点距离仍只是暂定值;返回此类部分结果的接口必须将这些值与最终确定的结果区分开来。
为什么贪心选择是正确的
正确性论证建立在两个事实上。首先,每个有限的暂定距离都是从源点出发的一条实际路径的长度,因此它是最优值的上界:
其次,一旦某个顶点的最短距离被确定,其距离值就是准确的。第二个性质是核心的循环不变量:在每次迭代开始时,每个已确定最短距离的顶点 都满足 。
假设该不变量成立,令 为尚未确定最短距离的顶点中暂定距离最小的顶点。考虑一条从 到 的最短路径。如果 ,令 为这条路径上第一个尚未确定最短距离的顶点,令 为它的前一个顶点。顶点 的最短距离已经确定。在处理 时,算法对从它到 的边进行了松弛。最短路径的任意前缀本身也是到其终点的最短路径,因此这次松弛使得 。
这条路径剩余部分的所有边权都非负。因此,
由于 在所有尚未确定最短距离的顶点中具有最小的暂定距离,
结合上界性质 ,便可证明两者相等。因此,确定 的最短距离不会破坏该不变量。初始化保证源点满足要求,再通过归纳即可证明,之后每个被确定最短距离的顶点,其距离值都是正确的。
这一证明解释了为什么允许边权为零。所需的不等式是非严格不等式:在一条最短路径上,靠后的顶点与靠前的顶点到源点的距离可以完全相同。对于键值相等的顶点,可以按不同顺序确定其最短距离,而不会改变最终的距离值。不过,前驱树仍可能因平局处理方式和邻接顶点的遍历顺序不同而有所差异。
负权会使上述关键不等式失效。例如,设有边 ,权重为 2;边 ,权重为 5;以及边 ,权重为 。算法会在考察 之前,就将 的最短距离确定为 2,尽管经过 的路径代价为 1。这个图甚至不包含任何环:即使没有负权环,标准算法也可能失效。
如果某种变体会反复将已确定最短距离的顶点重新置为未确定状态,那么上述证明和通常的运行时间界就不再适用。真正的要求不只是不存在负权环,而是在所采用的距离表示方式下,各条边的代价都必须非负。这一区别在形式验证中十分重要,因为输入假设、算术运算行为、队列操作和不变量都必须与实现相符。
实例演算与输出解读
考虑一个有向图,其源点为 ,其余顶点为 。图中的边包括:权重为 4 的 、权重为 1 的 、权重为 2 的 、权重为 5 的 、权重为 1 的 、权重为 7 的 ,以及权重为 3 的 。初始时,只有源点的暂定距离是有限值。
将 定型后,发现到达 的距离为 4,到达 的距离为 1。下一个定型的顶点是 ,而非 ,因为选择依据是从源点出发的总距离。对 的出边进行松弛,将到达 的距离改进为 ,并发现到达 的距离为 。因此,先前找到的直达 的路径,在 定型之前就被替换了。
各步的距离标号如下:
| 刚定型的顶点 | |||||
|---|---|---|---|---|---|
| 初始状态 | 0 | ||||
| 0 | 4 | 1 | |||
| 0 | 3 | 1 | 6 | ||
| 0 | 3 | 1 | 4 | 10 | |
| 0 | 3 | 1 | 4 | 7 | |
| 0 | 3 | 1 | 4 | 7 |
当 以距离 3 定型时,它将到达 的距离从 6 改进为 4,并发现到达 的距离为 10。随后,将 定型又把到达 的距离改进为 7。最终,到达 的最短路径为 。这条路径包含四条边,而只有三条边的路径 的代价反而更高。迪杰斯特拉算法最小化的是总权重,而不是边数。
前驱关系为 、、 和 。这些关系共同构成一棵以 为根、仅包含可达顶点的树。原图可以包含环和许多其他边;这种表示最优路径的方式并不需要纳入那些边。
如果将权重为 5 的边替换为权重为 3 的边 ,那么到达 就会有两条代价均为 4 的最短路径:一条从 直接延伸到 ,另一条经过 。仅在距离严格减小时才更新的实现,会保留最先使距离达到该值的前驱。若要保留所有同样最优的前驱,则需要额外的逻辑。
存在零权重环时,这一区别尤其重要。每个顶点只保留一个前驱,仍然可以表示一棵最短路径树;但所有保持最短距离的边组成的集合却可能包含环。反复经过这样的环,可能产生无穷多条最优游走,尽管有限图中的简单路径只有有限多条。因此,计算距离、返回一条最优路径和枚举所有最优路径,是不同的计算任务。
数据结构与计算复杂度
该算法的时间复杂度取决于如何选取距离最小的顶点,以及如何存储出边。设 ,。一种简单的实现方式是在每轮迭代中扫描所有尚未确定最短距离的顶点,从中找出距离最小者。选取操作的总时间开销为 ,检查边还需 时间。对于简单图,最终的复杂度上界通常写作 。对于稠密图和规模不大的问题,这种实现仍然很实用。
邻接表只存储实际存在的边,使算法能够在与顶点出度成正比的时间内检查一个已确定最短距离的顶点的所有出边。结合带索引的二叉堆,取出最小元素和减小键值操作各需 时间。取出操作至多有 次,成功的键值减小或插入操作至多有 次,因此时间复杂度为
对于至少有两个顶点的连通无向图,,因此这一上界常简写为 。
斐波那契堆的减小键值操作具有 的摊还时间复杂度,取出最小元素操作具有 的摊还时间复杂度,由此得到经典的复杂度上界
迈克尔·弗雷德曼和罗伯特·塔扬在1987年发表的研究中提出了斐波那契堆。其理论优势并不意味着它在实际应用中总是更优:大量使用指针的结构、内存分配和缓存行为所带来的开销,可能抵消渐近操作次数减少所带来的收益。在常见工作负载下,更简单的堆往往表现良好。
许多实现完全避免使用减小键值操作。每当找到更短的距离时,就将包含该距离和对应顶点的新二元组插入堆中。先前的条目仍保留在堆内;取出时,若其中存储的距离与该顶点当前的距离标号不一致,就将其丢弃。这种惰性实现对每次成功的松弛至多执行一次插入,此外还需插入一次源点。其队列可能占用 空间,一般情况下的时间复杂度上界为 。对于简单图,通常使用 来表示这一上界。
对边权的限制可以支持进一步的专门优化。如果每条边的权重均为1,广度优先搜索无需使用堆,即可在 时间内解决问题。如果边权只有0和1,则可借助双端队列实现一种线性时间算法,通常称为0–1 BFS。对于取值范围有界的非负整数边权,桶队列可以利用键值范围受限这一特点。基数堆则同时利用了键值为整数,以及依次取出的最小距离不会减小这两个性质。
图以邻接表形式存储时,通常需要 空间。距离、前驱、最短距离已确定标记以及带索引的队列,另需 辅助空间。实际开销还取决于存储顶点标识符所用的数据结构,以及边权能否用定长机器字表示;上述标准复杂度上界假定算术运算和比较均可在常数时间内完成。
实现细节与数值可靠性
即使抽象算法本身正确,也可能因队列处理、算术运算或含糊的输出约定而在实现中出错。使用惰性堆时,必须先检查取出的条目,再处理其顶点的出边。一种典型的检查方式是:当 时,丢弃条目 。另一种做法是维护顶点是否已确定最短距离的标记,跳过已经确定的顶点。在某些实现中,反复处理过期条目可能不会影响距离的正确性,但会破坏预期的效率,并使提前终止的处理更加复杂。
定长整数溢出是一个尤为严重的问题。如果一个很大的正距离加上边权后发生回绕,变成负值或较小的值,算法就可能将一条代价极高的路径误认为最优路径。因此,必须确保表示无穷大的哨兵值与有限距离能够安全地区分开来,并保证加法结果不超出支持的数值范围,或者显式检查溢出。任意精度整数可以避免溢出,但其算术运算的开销取决于各个数值的位数。
浮点边权会带来另一类限制。在证明中,非负实数的数学加法是精确的,而机器加法通常会进行舍入。原本不同的路径代价可能因此变得无法区分,不同的加法顺序也可能得到略有差异的结果。实现应当明确规定所采用的数值模型,而不是默默地将浮点运算结果视为精确的实数运算结果。NaN 值尤其不适用,因为涉及它们的比较无法形成堆所要求的顺序关系;对于无穷大值,也必须明确其含义。
平局处理规则会影响结果的可复现性。如果两个顶点的暂定距离相同,可以先确定其中任意一个,但最终得到的前驱树可能取决于堆的行为、输入顺序或顶点标识符。增加次级排序规则可以使选择过程具有确定性。若松弛操作仅在距离严格减小时才更新,那么代价相同的备选路径不会替换已有前驱。如果不考虑零权边和前驱管理,就将判断条件从 改为 ,可能导致不必要的更新,或使路径重建出现问题。
在整个搜索过程中,图还必须始终与所采用的代价模型一致。如果算法已经确定了相关顶点的最短距离,之后某条边的权重又发生变化,那么不变式可能不再成立。对于动态网络,需要使用一致的快照、重新计算,或采用专门的更新方法。同样,如果一条无向边在两个方向上的代价不同,最好将其建模为两条有向边,而不是赋予它一个对称的权重。
测试时可以利用能够独立验证的性质,而不只是依赖已知示例。算法运行结束后,每条可达边都应满足
每个可达的非源顶点都应有一条使上述不等式取等号的前驱边,而且沿其前驱链应能到达源点。这些条件,加上 以及对不可达顶点的适当处理,便构成了最短路径距离的正确性凭证:边上的不等式给出了所有路径代价的下界,而前驱路径则证明所报告的数值确实可以达到。
与其他最短路径方法的关系
迪杰斯特拉算法在最短路径算法中有其特定的适用范围,并不能取代所有其他方法。广度优先搜索是它在所有边权均为单位权重时的对应算法:顶点按经过边数相同的层次依次处理,因此使用先进先出队列就足够了。在人工智能搜索的术语中,一致代价搜索将同样的“优先处理累计代价最小者”原则应用于状态空间;这个状态空间可以在探索过程中逐步生成,而不必以完整图的形式预先存储。对于无限状态空间,完备性还需要额外条件;仅凭算法在有限图上的正确性,并不能判定搜索是否会终止。
贝尔曼–福特算法允许边权为负,并能检测从源点可达的负权环。它通常的最坏情况运行时间为 。该算法反复传播距离的改进,而不是按照迪杰斯特拉算法的顺序逐一永久确定顶点的距离。有向无环图还有另一种求解方式:按拓扑顺序处理顶点,即可在 时间内求解单源最短路径,即使部分边权为负也不例外,因为图中不存在会使依赖顺序复杂化的有向环。
A星搜索引入面向目标的启发式方法,以 表示其估计值,并按下式对顶点排序:
其中, 是当前已知从源点到该顶点的最小代价。当 恒为零时,便得到迪杰斯特拉算法。一致的启发式函数满足 ,从而使约化代价 非负。这使 A星搜索与迪杰斯特拉算法的标号确定原则直接联系起来。在图搜索实现中,可采纳但不一致的启发式函数可能导致已关闭的顶点需要重新打开。
重赋权也是求解全点对最短路径的约翰逊算法的基础。当有向图中不存在负权环时,可通过一次贝尔曼–福特算法计算得到顶点势,将边权转换为非负的约化权重。随后,以每个顶点为源点分别运行迪杰斯特拉算法,再利用势将所得距离还原为原始权重下的距离。对于稠密图上的全点对最短路径问题,弗洛伊德–沃舍尔算法则使用动态规划和距离矩阵,时间复杂度为 。
迪杰斯特拉算法也与求最小生成树的普里姆算法相似,但两者的优化目标不同。普里姆算法的优先级衡量的是将某个顶点连接到当前不断扩展的树上的最小单边代价。迪杰斯特拉算法的优先级衡量的则是从源点出发的整条路径的最小代价。最短路径树的边权总和未必最小,而最小生成树也未必保持从源点到各顶点的最短距离。
双向迪杰斯特拉算法同时进行两次搜索:一次从源点正向搜索,另一次从目标点反向搜索;在有向图中,反向搜索使用反向边。正确的终止条件取决于一个界,而不能仅以两次搜索首次相遇为准。一种标准条件是,将目前找到的最佳完整路径的代价,与正向和反向搜索中尚未确定的最小距离之和进行比较;一旦这个下界表明不可能再找到代价更小的路径,搜索就可以停止。
路由、导航与扩展模型
链路状态路由是该算法的一项重要应用。在 开放最短路径优先 协议中,路由器利用链路状态信息构建网络拓扑表示,并计算以自身为起点的最短路径。边权表示配置的路由开销,不一定是物理距离或当前时延。得到的最短路径结构有助于确定下一跳。等开销的备选路径可以支持多个下一跳,因此,路由实现所需的输出可能比单棵前驱树更丰富。
这种用途应与覆盖整个互联网的域间路由区分开来。边界网关协议在自治系统之间交换可达性和路径信息,并依据策略选择路由;它并不是简单地在整个互联网上运行迪杰斯特拉算法。即使在链路状态系统内部,最短路径计算也只是其中一个组成部分,其他部分还包括拓扑信息分发、故障检测、协议状态维护以及转发表安装。
道路导航是另一个主要应用场景。顶点可以表示交叉路口,边可以表示路段,权重则基于路段长度或预计通行时间。单行道可以自然地表示为有向边。转向限制揭示了仅用路口建模的简单模型所存在的局限:能否从某个方向驶离路口,以及相应的代价,可能取决于车辆从哪条道路驶入。因此,可以扩展状态,将驶入的有向路段也纳入其中,从而用带有相应代价的状态转移表示允许的转向及其额外开销。
对于规模庞大且大体稳定的道路网络,如果需要反复查询,普通的迪杰斯特拉搜索可能会探索过多顶点。收缩层次等预处理方法通过添加捷径边,在保持最短路径距离不变的同时,使查询只需考察小得多的搜索区域。这类方法仍与迪杰斯特拉式搜索密切相关,但以预处理时间和额外存储空间为代价,换取更快的查询速度。当权重或道路可通行情况频繁变化时,这种权衡也会随之改变。
多源搜索将多个源顶点的初始距离设为零。它计算到最近源点的距离,并可将每个到达的顶点分配给距离最近的设施。等价的做法是添加一个新的超级源点,用零权边将其连接到每个原有源点。这可用于基于网络的服务区域计算。在图像网格上,顶点可以表示像素或体素,非负的转移代价则可由局部图像特征或允许的移动方式确定;由此得到的距离取决于图模型,并不天然就是精确的欧几里得距离。
更复杂的目标需要额外假设或不同的算法。在时变路由中,若满足先进先出条件,即沿一条边较晚出发不可能比较早出发更早到达,那么标签设定方法就可以适用。对于带资源约束的路径规划,例如在燃料限额内最小化行程时间,如果不扩展状态,通常无法仅用每个物理顶点上的一个标量距离来表示。同样,存在多个相互竞争的目标时,可能需要维护非支配标签集合。迪杰斯特拉原理是否适用,取决于所选的状态与代价表示能否保持安全地将标签定型所需的序关系性质。