Dijkstra算法 vs Bellman-Ford算法

两种单源最短路径算法分别以贪心和逐步松弛策略求解，在边权要求、效率和功能上各有侧重

共同点

• 都解决单源最短路径问题（Single-Source Shortest Paths）
• 都基于松弛操作（RELAX）作为核心步骤
• 都维护距离估计值 $d[v]$ 和前驱 $\pi [v]$
• 都输出最短路径树（前驱子图 $G_{\pi }$）
• 都要求图中不存在从源点可达的负权环（否则最短路径无定义）

关键区别

维度	Dijkstra算法	Bellman-Ford算法
边权要求	所有边权必须非负（$w(u,v)\ge 0$）	允许负权边
数据结构	优先队列（最小堆）	简单数组（无需特殊数据结构）
时间复杂度	$O((V+E)\lg V)$（二叉堆） $O(V\lg V+E)$（斐波那契堆）	$\Theta (VE)$
负权环检测	不支持（算法本身不检测）	支持（第 $\Vert V\Vert$ 轮检查）
贪心 vs DP	贪心策略（每次选最近顶点）	动态规划（逐步扩展路径边数）
松弛方式	只松弛取出顶点的出边	每轮松弛所有边
顶点处理顺序	按距离递增顺序（优先队列）	无特定顺序（遍历所有边）
适用场景	非负权图（如道路网络、无负权通信网络）	含负权边的图（如金融汇率网络）
稠密图	$O(V^2)$（数组实现）	$O(V^3)$（$V$ 次运行时）
稀疏图	$O(E\lg V)$（二叉堆）	$O(VE)$

深层联系

两种算法的核心差异在于贪心选择是否安全：

• Dijkstra的贪心选择依赖”已确定最短路径的顶点不会被后续更新”这一性质。当所有边权非负时，$\delta (s,u)\ge \delta (s,y)$ 成立（$y$ 是最短路径上第一个未确定顶点），因此取出 $u$ 时 $u.d=\delta (s,u)$。负权边会破坏此不等式。

• Bellman-Ford不依赖贪心选择，而是通过 $\Vert V\Vert -1$ 轮全边松弛逐步逼近。第 $i$ 轮后找到所有最多 $i$ 条边的最短路径。这种方式不要求边权非负，但效率较低。

在Johnson算法中，两者被巧妙结合：先用Bellman-Ford（一次）消除负权边，再用Dijkstra（$V$ 次）高效求解，兼得两者的优势。

参见

• 松弛操作
• 最短路径树
• Johnson算法