7.2 路径、连通、树与最短路：不同权重需要不同算法
导航中的“最短”可能指距离、时间、费用或换乘次数。选算法之前，要先确定路径成本怎样累加、边权能否为负、图是否有向，以及需要一个源点还是所有点对。
Walk、Trail、Path 和 Cycle
术语约定在教材间略有差异，本课采用：
- Walk（游走）：相邻顶点由边连接，可重复顶点和边；
- Trail（迹）：不重复边；
- Path（简单路径）：不重复顶点；
- Cycle（环）：不重复边的闭合游走，除首尾重合外顶点不重复；无向简单图中的环至少有 3 条边。
算法中常把一般顶点序列也口语称作 path。证明时应说明是否允许重复。
路径长度在无权图中常指边数；带权图中路径权重是沿途边权之和。
连通分量
无向图中，若任意两点间都有路径，图连通。包含零长度路径的可达关系是等价关系，其等价类就是连通分量。
有向图区分：
- 强连通：任意
u,v都能互相到达； - 弱连通：忽略方向后连通。
单向可达不等于强连通。服务 A 调用 B，B 不必能调用 A。
树的等价刻画
对至少有一个顶点的有限无向简单图，以下条件各自都等价于“该图是树”：
- 连通且无环；
- 任意两顶点间恰有一条简单路径；
- 连通且有
|V|-1条边； - 无环且有
|V|-1条边； - 连通，且删除任意边都会不连通；
- 无环，且加入任意一条连接原本不相邻顶点的新边都会产生唯一环。
这些等价性质让证明可以选择最方便的入口。
最后两条的前提不可省：森林中的每条边也都是桥，但森林可能不连通；已有环的图也不能靠“加边会成环”来证明它是树。单顶点、零条边的图是树。
树指定根后产生父子、深度和子树结构；无根树本身没有天然“上方”。文件目录通常按根树理解，但硬链接、符号链接和挂载会破坏简单树模型。
生成树与最小生成树
连通无向图的生成树包含全部顶点，并从原图选择 |V|-1 条边保持连通。
带权图的最小生成树（MST）使总边权最小。它优化的是“连接所有顶点的总成本”，不是任意两点间的最短路径。
Kruskal
- 按边权从小到大排序；
- 依次加入不会形成环的边；
- 用并查集维护连通分量。
Prim
- 从一个顶点开始维护当前树；
- 每次加入跨越当前树与外部的最小权边；
- 用优先队列维护候选边。
割性质要求先明确已选边：若已选边可扩充成某棵 MST，且一个割没有切断任何已选边，那么跨割的任意最轻边都能安全加入，使结果仍可扩充成某棵 MST。边权相同可能对应多棵同权 MST；最轻边不一定在所有 MST 中。
MST 通常针对无向图。网络布线若要求方向、可靠性冗余或容量，普通 MST 模型可能过弱。
例如三角形 AB=2,AC=2,BC=1，MST 可取 AB,BC，总重 3；其中 A 到 C 路径重 3，但原图直接边 AC 只需 2。负权边也不妨碍 MST 的割性质；不连通图则应求最小生成森林。
无权最短路：BFS
每条边成本相同且非负，BFS 按边数分层访问：
第 0 层：源点
第 1 层：一条边可达
第 2 层：两条边可达
...第一次发现顶点时，任何更短路径都应在更早层发现，因此得到最少边数路径。
边权为 0 或 1 时，可使用双端队列的 0-1 BFS；普通 FIFO BFS 不再足够。
非负权最短路：Dijkstra
Dijkstra 维护暂定距离：
dist[s]=0
其他 dist=∞每次从优先队列取暂定距离最小的顶点，并松弛出边：
if dist[v]+w(v,u)<dist[u]:
dist[u]=dist[v]+w(v,u)
parent[u]=v算法正确性依赖边权非负：当最小暂定顶点被确定时，绕经尚未确定顶点的路径不可能再把它变短。
有负边时，顶点确定后不再修改的贪心结论失效。允许已处理顶点反复入队的版本，在没有负环的条件下仍可能作为标签修正算法得到正确结果，但标准 Dijkstra 的多项式时间界不能照搬。下面的实现明确拒绝负权。
一个反例是 S→A:2,S→B:5,B→A:−4：把 A 以距离 2 确定后不再更新的版本会错过实际最短距离 1。提前在取出目标 A 时返回也会犯同样错误。
邻接表配二叉堆的常见复杂度：
O((V+E) log V)具体取决于优先队列实现和是否支持 decrease-key。常见工程实现重复入队，取出陈旧条目时跳过。
下面的 Python 3 示例限定非负整数边权、字符串顶点、已包含所有邻居键的有限静态图，且源点存在。它返回距离；若需要具体路径，可在松弛成功时同步记录前驱：
from heapq import heappush, heappop
from math import inf
def dijkstra(graph, source):
if any(weight < 0 for edges in graph.values() for _, weight in edges):
raise ValueError("nonnegative weights required")
distance = {v: inf for v in graph}
distance[source] = 0
heap = [(0, source)]
while heap:
cost, v = heappop(heap)
if cost != distance[v]:
continue # An improved entry has superseded this one.
for u, weight in graph[v]:
candidate = cost + weight
if candidate < distance[u]:
distance[u] = candidate
heappush(heap, (candidate, u))
return distance
graph = {"S": [("A", 10), ("B", 1)], "A": [],
"B": [("A", 1), ("C", 0)], "C": [], "U": []}
result = dijkstra(graph, "S")
print(result["A"], result["C"], result["U"]) # 2 1 infA 先以距离 10 入队，随后改进到 2；旧的 10 被取出时跳过。零权边合法，U 不可达。重复入队的堆最多保留 O(E) 条目，常用一般界为 O(V+E log(E+1))；简单图中可写为 O((V+E)log(V+1))。这与支持 decrease-key、堆只含 O(V) 个顶点的实现不同。
负边与负环：Bellman–Ford
Bellman–Ford 对全部边重复松弛，能处理负权边，并检测从源点可达的负环。
若负环从源点可达，则环上以及能从该环继续到达的目标没有有限最短游走权重；其他目标仍可能有有限距离，未必整张图的每个查询都失效。例如 S→A:1,A→B:−2,B→A:0,S→T:5 中，A、B 受负环影响，T 仍只有距离 5 的路径。若额外要求路径不重复顶点，就成了另一个优化问题。
典型复杂度：
O(VE)比 Dijkstra 慢，但模型能力不同。选择算法不能只按跑分，还要按边权假设。
DAG 最短路
有向无环图可按拓扑序处理顶点，每条边只需松弛一次：
O(V+E)DAG 即使有负边也不会有负环，因此算法仍可工作。任务成本、流水线关键路径常适合这一模型。
最长关键路径要把最小值松弛改为最大值松弛，并明确任务耗时记在节点还是边上；不能直接把最短路输出当项目工期。
所有点对与多目标成本
若需要所有点对最短路，可考虑 Floyd–Warshall O(V³) 或多次单源算法，选择取决于稠密度、负边和图规模。
现实导航常有多个目标：时间、费用、风险。把它们强行加成一个权重需要业务给出可解释的换算；否则应寻找 Pareto 前沿，而不是宣称存在唯一“最短”。
边权若随时间变化，静态最短路也可能失效。FIFO 时间依赖、等待和实时更新需要专门模型。
完成检查
- 证明树有
|V|-1条边； - 对同一带权图手工执行 Kruskal 和 Prim；
- 构造负边使 Dijkstra 失败的例子；
- 用 Bellman–Ford 判断一个负环是否从源点可达；
- 为 DAG 计算最短路和最长关键路径；
- 说明 MST 与从总部到每个站点的最短路树为何不同。