dijkstra寻路算法的节点松弛条件

### Dijkstra算法中的节点松弛

在Dijkstra算法中，节点松弛是指当发现了一条到达某节点更短的路径时更新该节点的距离估计值的过程[^1]。具体来说，对于当前正在处理的节点u及其邻接点v，如果从起始节点到u再到v的距离小于已知最短距离，则更新v的最短距离。

#### 松弛操作的具体实现

为了更好地理解这一过程，下面给出Python代码来展示如何执行松弛操作：

def relax(u, v, weight_uv, distances):
    # 如果通过边uv可以得到更短路径则更新distances[v]
    if distances[u] + weight_uv < distances[v]:
        distances[v] = distances[u] + weight_uv

此函数接收四个参数：`u`表示当前节点；`v`为目标邻居节点；`weight_uv`代表连接这两个节点之间的权重；而`distances[]`数组存储着从源点出发至各顶点的最佳（最小）成本记录。一旦满足上述不等关系即意味着找到了新的较佳路线，因此应当调整对应位置上的数值以反映最新情况。

#### 实际案例说明

假设有一个加权有向图G=(V,E)，其中包含五个城市作为顶点{A,B,C,D,E}以及它们之间相互连通的道路构成边集E。现在要寻找由城市A前往其余各地间的最优行程方案。初始状态下设所有未知路程长度均为无穷大∞除了起点外自定义为0。随着程序迭代推进不断尝试优化各个可能抵达地点的成本直至完成整个搜索流程为止。

| 城市 | A | B | C | D | E |
|------|----|----|----|----|----|
| 初始距离 | 0 | ∞ | ∞ | ∞ | ∞ |

经过一系列比较运算之后最终得出如下表所示的结果：

| 城市 | A | B | C | D | E |
|------|----|----|----|----|----|
| 最终最短距离 | 0 | 7 | 9 | 20 | 28 |

在这个过程中每当遇到能够降低目标结点预估值的情形就会触发一次所谓的“松弛”。比如最初认为去往B城至少需要花费10单位代价后来却发现经停C转道反而只需支付7个单位费用于是便进行了相应的修正动作使得整体规划更加经济高效[^2]。