💻 CSC4120 Week 8 最短路径问题

Lithos

CSC4120 W08 最短路径问题

I. Bellman-Ford Algorithm

Shortest Path Problem

给定一个带权有向图：G = (V, E)，w(u, v) 权重可以为一切整数

δ(s, c) 表示从 s 到 c 最短权重和 Shortest Distance，δ 的数值唯一但对应最短路径不一定唯一。如不可达，记作 δ = ∞

Single-Source Shortest Path (SSSP)：起点固定时简写为 δ(v)，π(v) 表示最短路径上 v 的前驱节点。前驱指针可以帮助我们重建完整路径：从终点不断沿着 π 向前直到起点。



Optimal Substructure & Bellman Equation

Sub-paths of shortest paths are also shortest paths 最短路径的子路径也必须最短

s ⇝ u ⇝ t：若有更短 (s, u) 可以替换当前路径，那 (s, t) 就不是最短

对于任意三个节点有三角不等式 δ(s, t) ≤ δ(s, u) + δ(u, t)，如果 u 位于某条最短路径上，等号成立

Bellman Equation：从 s 到 t 的最短路径，最后一步必然来自某个前驱节点 π[v] = u —— δ(t) = min {δ(u) + w(u, t)} 到达 t 的最短距离，等于所有可能的最后一步中，总距离最小的那个

问题是我们并不一定知道 δ(u) —— 先猜一个保守的值，然后不断改进。


负权边和负权环

负权边并不一定有问题，问题在于 Negative Cycle 负权环会破坏最短路径存在性：越绕权重和无限减小。因此对能够从 s 到达、并且可以从该负环继续到达的终点，最短路径权重没有有限最小值，通常记为 -∞。

没有负权环时只需考虑 Simple Path (不重复节点的路径)：如果一条路径重复了节点，那么中间一定存在一个 Cycle，当没有负权环时，这个 Cycle 的权重非负。删去这个 Cycle，不会增加路径总权重。所以我们总能找到一条简单最短路径。

包含 V 个节点的 Simple Path 最多有 V-1条边—— Bellman-Ford 只需要 V-1 轮


Relaxation 松弛操作

我们不知道真正的 δ(v)，所以先维护一个估计值 d[v] (或记作 $\hat{\delta}(v)$)。初始化 d[s] = 0，d[v] = ∞ (v ≠ s)；检查一条边 (u, v) 后，如果 d[u] + w(u, v) < d[v] 说明经过 u 可以更便宜地到达 v，于是更新 d[v] = min{d[v], d[u] + w(u, v)} 更新成功则记录 π[v] = u。

  • 估计值 d 只能减小，不会增加；

  • 在不存在相关负权环时，估计值不会小于真正的最短距离：d[v] ≥ δ(v)；

    因为每一个有限估计值，都来自一条实际可行的路径。既然 δ(v) 已经是所有路径中最小的，它不可能比真正最短距离还小。称这种估计为 Safe Estimate 安全估计。



Bellman-Ford Algorithm

不断对所有边进行 Relaxation，直到不能再更新，最多 V-1 轮

每一轮至少可以让最短路径上下一层的节点获得正确的最短距离。

所以 Round 1 保证所有最短路径只含 1 条边的节点正确…… Round k 保证所有最短路径最多含 k 条边的节点正确。

⚠️ 每一轮可能让多个层次的节点同时得到正确答案。检查顺序恰好沿最短路径方向 s⇝v，一轮就能把整条路径更新完。最差情况 (V-1)就是完全逆序。

def bellman_ford(G, s):
    for v in G.V:
        d[v] = float("inf")
        parent[v] = None
    d[s] = 0
    for _ in range(len(G.V) - 1):
        for u, v, w in G.E:
            if d[u] != float("inf") and d[u] + w < d[v]:
                d[v] = d[u] + w
                parent[v] = u
    # One additional pass: detect reachable negative cycles
    for u, v, w in G.E:
        if d[u] != float("inf") and d[u] + w < d[v]:
            return "Reachable negative cycle"
    return d, parent

如果不存在可达负权环，那么经过 V-1 轮后，所有最短距离已经正确，无法再成功松弛。如果第 V 轮还能找到松弛，说明存在可达负权环。


Time Complexity & Example

初始化 O(V)，遍历所有边 O(E) 共进行 V-1 轮，最后检查负权环再遍历一次 O(E)：O(V + VE + E) = O(VE)

Sparse (E = Θ(V))：Θ(V2)；Dense (E = Θ(V2))：Θ(V3)

💻 CSC4120 Week 8 最短路径问题 相关图片

Round 1：从源点 0 的直接出边得到 d[1] = 6，d[2] = 5，d[3] = 5

Round 2： 4, 5 可达，然后通过负权边 d[2] + w(2, 1) < d[1] 和 d[3] + w(3, 2) < d[2] 更新 d[1] = 3, d[2] = 3，且 π[1] = 2，π[2] = 3

Round 3：上一轮 d[1]、d[2] 更新，故本轮 d[4] 可以更新，同时 6 可达

……

⚠️ 每轮只能探索已发现节点出发的边 (第一轮时只有 s)；

⚠️ 对于 (u, v) 每次用 Relaxation 更新 d[v] 时使用的是上一轮的 d[u] 值，即使本轮 d[u] 有更新。




II. Dijkstra DAGs

comments powered by Disqus