1. 引言
本文将深入讲解 Dijkstra 算法中“边松弛（Edge Relaxation）”的核心机制。边松弛不仅是 Dijkstra 算法的关键步骤，也是许多图论中最短路径算法的重要组成部分。
2. 最短路径的寻找
最著名的最短路径应用之一是导航系统。在地图中寻找两个位置之间的最短路径是其典型场景：
如图所示，这是一个简单的最短路径问题，从东京出发，经过北京到达纽约是最短路径。
寻找最短路径的计算成本可能很高。设想在一个城市之间错综复杂的导航系统中，寻找两点之间的最短路径。Dijkstra 算法因其高效性而广为人知，它适用于没有负权边的有向图。
3. 通过边松弛优化路径
Dijkstra 算法和 Bellman-Ford 算法都使用了一种称为“边松弛”的技术。其核心思想是在图的遍历过程中，不断发现更短的路径并更新已有路径的代价。
来看一个具体例子：
我们从节点 A 出发，目标是 E。按照 Dijkstra 算法流程，我们首先从 A 到达 C，此时 A 到 D 的总代价为 16。但 Dijkstra 会优先选择当前最短的边，因此它会先选择 A→B。从 B 出发，我们发现 A→B→D 的代价为 11，比 A→C→D 更优。于是我们更新 D 的最短路径代价为 11。
✅ 这个更新路径的过程就被称为“边松弛”。
4. 时间复杂度分析
在图中尝试所有可能路径是一个超多项式问题。因此，一个高效的最短路径算法能节省大量时间。
- Dijkstra 算法使用列表实现时，时间复杂度为 O(V²)
- Bellman-Ford 算法使用边松弛，时间复杂度为 O(VE)
还有一种不使用边松弛的最短路径算法是 Floyd-Warshall 算法，它用于计算图中所有点对之间的最短路径，时间复杂度为 O(V³)，适用于带负权边的图。
⚠️ 由此可见，边松弛技术在性能上带来了显著优势。
5. 松弛顺序的重要性
虽然 Dijkstra 和 Bellman-Ford 都使用边松弛，但它们的复杂度不同。这说明：不仅松弛本身重要，松弛的顺序也至关重要。
来看一个例子：
我们依次松弛 A→B、B→C、C→D、D→E 边：
然后我们发现可以松弛上右的边，得到更短的 E 路径：
接着松弛上左的边，优化 C 的路径：
最后再次松弛上右的边，得到最终的最短路径：
✅ 可以看出，松弛顺序不同，松弛次数也会不同。在某些情况下，不当的顺序可能导致额外的 O(n!) 松弛操作。
6. 总结
本文深入探讨了 Dijkstra 算法中“边松弛”的概念及其在最短路径算法中的关键作用。我们还分析了不同松弛顺序对计算效率的影响，并通过图示和示例说明了其实际意义。
边松弛不仅是一个技术术语，更是优化最短路径算法性能的核心机制。掌握其原理和应用场景，对理解和实现高效图算法至关重要。