数据结构与算法 / 系统课时
最短路径问题建模
最短路径问题建模
最短路径的关键不是立即选择某个算法,而是先明确图的方向、边权含义、查询范围和不可达状态。本课将业务中的“最低代价到达”转成带权图,并用松弛操作维护距离估计与前驱关系,为后续算法选择建立统一模型。
学习目标
- 区分单点对、单源、多源与全源最短路径任务。
- 正确表示路径代价、不可达状态和前驱节点。
- 理解松弛操作的条件、结果与边界限制。
问题定义
将问题表示为带权图 :顶点集合 表示地点、状态或任务,边集合 表示允许的转移,边权 表示从 到 的代价。路径 的总代价等于路径上全部边权之和,最短路径是在候选路径中总代价最小的一条。
有向图只允许按边的方向移动;无向边在邻接表中通常要保存为两个方向。两个顶点之间没有可达路径时,距离应保持为正无穷,而不是误写成 0,因为 0 表示一条真实的零代价路径。
| 任务类型 | 已知条件 | 需要求解的结果 | 常见场景 |
|---|---|---|---|
| 单点对 | 起点和终点固定 | 一对顶点之间的最短距离或路径 | 一次路线查询 |
| 单源 | 起点固定 | 起点到所有可达顶点的结果 | 导航、广播延迟 |
| 多源 | 多个起点 | 任一源点到各顶点的最优结果 | 最近服务点、多个入口 |
| 全源 | 所有顶点都可作为起点 | 任意两点之间的结果 | 小规模网络分析 |

松弛操作
算法通常为每个顶点维护距离估计 distance[v]。起点初始化为 0,其余顶点初始化为正无穷。检查边 时,若 distance[u] + weight < distance[v],就用更小的候选值更新 distance[v],并把 u 记录为 v 的前驱。
一次松弛只证明“发现了一条更短的已知路径”,不一定已经得到最终答案。不同算法的区别主要在于以什么顺序选择边或顶点、何时可以确认距离已经不会再变,以及能否处理负权边。
负权边并不等同于负权环。图中可以存在负权边且仍有有限最短路径;但只要从起点能够到达一个总权重为负的环,就可以不断绕环降低代价,此时相关顶点不存在有限最短距离。
可运行示例
下面的 Python 程序对全部边重复执行松弛,并使用前驱表还原从 A 到 D 的路径。示例图没有负权环,因此最多经过 轮后距离稳定。
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,然后运行:
python shortest_path_model.py预期输出
最短距离: {'A': 0, 'B': 3, 'C': 1, 'D': 4}
A 到 D: A -> C -> B -> D输出表明,直接边 A -> B 的代价为 4,但经过 A -> C -> B 后可降为 3;继续松弛 B -> D,最终得到总代价 4 的路径。该示例采用边表反复扫描,时间复杂度为 ,距离表和前驱表额外占用 空间。
常见错误
- 把边数当作顶点数。数组和循环边界必须分别根据
V与E建模,否则容易遗漏顶点或越界。 - 用 0 表示不可达。这样会让所有正权候选值都无法更新,应使用正无穷或足够大的安全上界。
- 只保存距离而不保存前驱。这样能回答最短代价,却无法还原具体路径;每次成功松弛时应同步更新
previous[v]。 - 未确认负权条件就选择算法。Dijkstra 算法要求边权非负;存在负权边时应改用能够处理该条件的方法。
本课练习
- 将示例中的边
C -> D权重改为 2,运行程序并核对A到D的最短距离与路径是否同步变化。 - 为图增加顶点
E,但不添加任何指向E的边。要求输出时明确显示E不可达,并避免尝试还原一条不存在的路径。 - 设计一个包含负权边但不含负权环的有向图,手工记录每轮松弛后的距离表,再与程序结果比较。
本课总结
- 最短路径建模必须同时明确图的方向、边权语义、查询范围和不可达表示。
- 松弛通过比较旧距离与候选距离逐步改进估计,并用前驱表保留路径结构。
- 边权是否为负、是否存在可达负权环,会直接决定问题是否有有限解以及应选择哪类算法。
下一课预告
下一课将学习 Dijkstra 算法,利用非负边权的性质和优先队列,优先处理当前距离最小的顶点,并正确跳过重复入队产生的过期队列项。