数据结构与算法 / 系统课时

最短路径问题建模

最短路径问题建模

最短路径的关键不是立即选择某个算法,而是先明确图的方向、边权含义、查询范围和不可达状态。本课将业务中的“最低代价到达”转成带权图,并用松弛操作维护距离估计与前驱关系,为后续算法选择建立统一模型。

学习目标

  • 区分单点对、单源、多源与全源最短路径任务。
  • 正确表示路径代价、不可达状态和前驱节点。
  • 理解松弛操作的条件、结果与边界限制。

问题定义

将问题表示为带权图 G=(V,E)G=(V,E):顶点集合 VV 表示地点、状态或任务,边集合 EE 表示允许的转移,边权 w(u,v)w(u,v) 表示从 uu 到 vv 的代价。路径 PP 的总代价等于路径上全部边权之和,最短路径是在候选路径中总代价最小的一条。

有向图只允许按边的方向移动;无向边在邻接表中通常要保存为两个方向。两个顶点之间没有可达路径时,距离应保持为正无穷,而不是误写成 0,因为 0 表示一条真实的零代价路径。

任务类型 已知条件 需要求解的结果 常见场景
单点对 起点和终点固定 一对顶点之间的最短距离或路径 一次路线查询
单源 起点固定 起点到所有可达顶点的结果 导航、广播延迟
多源 多个起点 任一源点到各顶点的最优结果 最近服务点、多个入口
全源 所有顶点都可作为起点 任意两点之间的结果 小规模网络分析

最短路径任务类型与松弛关系

松弛操作

算法通常为每个顶点维护距离估计 distance[v]。起点初始化为 0,其余顶点初始化为正无穷。检查边 (u,v)(u,v) 时,若 distance[u] + weight < distance[v],就用更小的候选值更新 distance[v],并把 u 记录为 v 的前驱。

一次松弛只证明“发现了一条更短的已知路径”,不一定已经得到最终答案。不同算法的区别主要在于以什么顺序选择边或顶点、何时可以确认距离已经不会再变,以及能否处理负权边。

负权边并不等同于负权环。图中可以存在负权边且仍有有限最短路径;但只要从起点能够到达一个总权重为负的环,就可以不断绕环降低代价,此时相关顶点不存在有限最短距离。

可运行示例

下面的 Python 程序对全部边重复执行松弛,并使用前驱表还原从 A 到 D 的路径。示例图没有负权环,因此最多经过 ∣V∣−1|V|-1 轮后距离稳定。

python
from math import inf

def relax(u, v, weight, distance, previous):
    # 不可达顶点不能产生有效候选路径。
    if distance[u] == inf:
        return False

    candidate = distance[u] + weight
    if candidate < distance[v]:
        distance[v] = candidate
        previous[v] = u
        return True
    return False

def rebuild_path(previous, target):
    if target not in previous:
        return []

    path = []
    current = target
    while current is not None:
        path.append(current)
        current = previous.get(current)
    path.reverse()
    return path

def main():
    vertices = ["A", "B", "C", "D"]
    edges = [
        ("A", "B", 4),
        ("A", "C", 1),
        ("C", "B", 2),
        ("B", "D", 1),
        ("C", "D", 5),
    ]

    distance = {vertex: inf for vertex in vertices}
    previous = {"A": None}
    distance["A"] = 0

    # 每轮完整扫描所有边,持续传播更短的距离估计。
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, weight in edges:
            changed = relax(u, v, weight, distance, previous) or changed
        if not changed:
            break

    # 额外检查一轮可以发现从起点可达的负权环。
    for u, v, weight in edges:
        if distance[u] != inf and distance[u] + weight < distance[v]:
            raise ValueError("存在从起点可达的负权环")

    print("最短距离:", distance)
    print("A 到 D:", " -> ".join(rebuild_path(previous, "D")))

if __name__ == "__main__":
    main()

将代码保存为 shortest_path_model.py,然后运行:

bash
python shortest_path_model.py

预期输出

text
最短距离: {'A': 0, 'B': 3, 'C': 1, 'D': 4}
A 到 D: A -> C -> B -> D

输出表明,直接边 A -> B 的代价为 4,但经过 A -> C -> B 后可降为 3;继续松弛 B -> D,最终得到总代价 4 的路径。该示例采用边表反复扫描,时间复杂度为 O(∣V∣∣E∣)O(|V||E|),距离表和前驱表额外占用 O(∣V∣)O(|V|) 空间。

常见错误

  1. 把边数当作顶点数。数组和循环边界必须分别根据 V 与 E 建模,否则容易遗漏顶点或越界。
  2. 用 0 表示不可达。这样会让所有正权候选值都无法更新,应使用正无穷或足够大的安全上界。
  3. 只保存距离而不保存前驱。这样能回答最短代价,却无法还原具体路径;每次成功松弛时应同步更新 previous[v]。
  4. 未确认负权条件就选择算法。Dijkstra 算法要求边权非负;存在负权边时应改用能够处理该条件的方法。

本课练习

  1. 将示例中的边 C -> D 权重改为 2,运行程序并核对 A 到 D 的最短距离与路径是否同步变化。
  2. 为图增加顶点 E,但不添加任何指向 E 的边。要求输出时明确显示 E 不可达,并避免尝试还原一条不存在的路径。
  3. 设计一个包含负权边但不含负权环的有向图,手工记录每轮松弛后的距离表,再与程序结果比较。

本课总结

  • 最短路径建模必须同时明确图的方向、边权语义、查询范围和不可达表示。
  • 松弛通过比较旧距离与候选距离逐步改进估计,并用前驱表保留路径结构。
  • 边权是否为负、是否存在可达负权环,会直接决定问题是否有有限解以及应选择哪类算法。

下一课预告

下一课将学习 Dijkstra 算法,利用非负边权的性质和优先队列,优先处理当前距离最小的顶点,并正确跳过重复入队产生的过期队列项。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最短路径问题建模

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通