# Weighted Shortest Paths
## 引言
在进入 Weighted Shortest Paths 问题之前，先回忆一下 Unweighted Shortest Paths 问题，事实上，后者可以理解为前者的一个特例 --- 每条边的权重为相同的正数。
## 最短路径问题（Shortest-paths Problems）
最短路径问题实际上由一组相互关联的问题组成：
* single-pair：找到图中两点之间的最短路径：$$δ(s, t)$$
* single-source：找到从图中某一点 s 出发到达图中所有其它点的最短路径，$$δ(s, t)$$ for all $$v \in{V}$$ ；即以 s 为根节点的最短路径树（shortest-path tree)。
* all-pairs：找到图中任意两点的最短路径：$$δ(s, t)$$ for all $$u, v \in{V}$$
#### 权重
即使图中的两点之间存在路径，这两点之间也可能不存在最短路径！--- 图中存在负权重环（negative-weight cycle）
#### 现实意义
最短路径问题是极具现实意义的问题：
* 地图导航
* 网络路由
大多数现实问题中，不同路径的成本通常不同，因此可以被抽象为 Weighted-shortest-paths Problems。
#### 特点
* Subpath Property：最短路径的任意子路径也是最短路径（如何证明？）
* Tree Property：从图中某点 s 出发到达图中其它所有可达点的路径恰好组成以 s 为根节点的树 T
#### 算法框架
1. 初始化： $$d = { s: 0, rest: ∞ }$$ , $$parent = {s: s}$$
2. 选择一条边 $$(u, v) \in{E}$$
3. relax $$(u, v)$$ (具体见下文)
4. 重复步骤 2, 3 直到没有 relaxation 发生为止
*Relaxation*
```python
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w(u, v)
parent[v] = u
```
relaxation：当前的解还不满足某些要求，尝试去修复解中不满足要求的部分
算法复杂度与 relaxation 的次数相关：
* 当图中存在 negative-weight cycle 时，将出现**无限次 relaxation**
* 使用暴力解法时，relaxation 次数通常呈现**指数增长，**如图 1 所示：
因此各种最短路径算法实际是在尝试减少 relaxation 次数的方法。
#### 算法证明
1. Safety Lemma: relax $$(u, v)$$ maintains invariant $$d\[v] \geqslant δ(s, v)$$
2. Termination Lemma: if no edge can be relaxed, then $$d\[v] = δ(s, v)$$ for all $$v \in {V}$$
### 有向无环图中的单起点最短路径问题（DAG-SSSP）
遇到 DAG 时，拓扑排序一定是个好主意，它可以找到图中个点的路径依赖关系。因此就有如下算法：
```
initialize
topologically_sort(G) # O(V+E)
for u in V: # 以拓扑排序的顺序遍历 O(V+E)
for v in Adj[u]:
relax(u, v)
```
正确性：设 A 为 S 到 T 的最短路径上的一点，按照拓扑顺序，在访问 A 之前，所有存在指向 A 路径的节点都已经被访问，因此从 S 到 A 的最短路径已经找出，依次类推。
### 有环图的单起点最短路径问题
当图中存在环，甚至负权重环时，SSSP 将面临更大的挑战，可能存在 $$\delta(s, v) = -∞$$ 的情况，这种情况下，我们希望算法如何输出？
* 版本1：检测出是否有负权重环，如果存在则认为输入错误
* 版本2：找到所有满足 $$\delta(s, v) = -∞$$ 的节点
* 版本3：找到其中一个负权重环
Bellmand-Ford 算法实现很简单，重复 $$|V| - 1$$ 轮 relaxation 操作，每轮都遍历并 relax 图上的所有边：
```python
initialize parent and d arrays
for round in range(|V|-1):
for edge(u, v) in G:
relax(u, v)
handle negative weight cycles somehow
return parent, d
```
**正确性**：
参考 course note, 关键在于想明白：**经过 i 轮 relaxation 操作后，所有节点数为 i 的最短路径都被找到**。同样的证明可以应用到 DAP-SSSP 问题中去。
**时间复杂度**： $$O（|V|\times|E|）$$
仔细推算，实际上是 $$O(|V||E| + |V|^2)$$
#### 版本1：检测负权重环是否存在
完成 $$|V|-1$$ 轮 relaxation 操作后，检测任何边是否仍然可以 relax，如果可以，就判断存在负权重环：
```python
initialize parent and d arrays
for round in range(|V|-1):
for edge(u, v) in G:
relax(u, v)
# Now check for neg-weight cycles
for edge(u, v) in G:
if d[v] > d[u] + w(u, v):
raise ValueError("There's a neg-weight cycle reachable from s!!!")
return parent, d
```
**正确性：**
根据刚才的推理，在第 $$|V|$$ 轮应当找到节点数为 $$|V|$$ 的最短路径，但不出现重复点的最短路径最多只能包含 $$|V|-1$$ 个节点。
**时间复杂度：**
最后检测操作复杂度为 $$O(|E|)$$ ，总体仍然为 $$O(|V||E|)$$
#### 版本2：找到所有 $$\delta(s, v) = -∞$$ 的节点
完成 $$|V|-1$$ 轮 relaxation 操作后，搜集所有可以 relax 的节点组成集合 N，N = { v | some edge (u, v) is relaxable} ，所有从 N 中的节点出发能到达的节点最短路径都为 $$-∞$$
```python
initialize parent and d arrays
for round in range(|V|-1):
for edge(u,v) in G:
relax(u,v)
# Now find verts with delta = -inf
N = {}
for edge(u,v) in G:
if d[v] > d[u] + w(u,v):
N.insert(v)
for v in multi_source_search(N):
d[v] = -math.infinity
parent[v] = None
return parent, d
```
其中 multi\_source\_search() 有多种实现方式：如 BFS，DFS 等等
正确性证明略，时间复杂度同上。
#### 版本3：找到一个负权重环
### 无负权重边的单起点最短路径问题
如果我们能够保证图中所有边的权重 w > 0，那么我们可以做得比 Bellman Ford 更好，即优于 $$O(|V||E|）$$。Dijkstra 算法能实现 $$O(|E| + |V|log|V|)$$ 的时间复杂度。
#### Dijkstra 的核心思想
从起点出发，向外有选择地拓宽边界，同时保证
* 在边界内的点都已经找到了最短路径
* 在边界外的点都已经找到只经过边界内的点可达的最短路径
Srini Devadas 在课堂上给出的 demo 非常震撼：如图 2 所示：他将一个图具象化为用线相连的球，线的长短表示图中边缘的权重，然后提起其中一只球 A，由于重力的原因，离球 A 最近的球 B 会先到达最低点，同时它们之间的线处于紧绷状态，而离球 A 第二近的球 C 会第二个到达最低点，它的最短路径上的线也会处于紧绷状态，如图 3 所示。如果用慢镜头来看，将可以看到每个球按顺序陆续达到最低点，及边界范围逐渐扩大的过程。用物理来解释算法，非常震撼！
#### Dijkstra 算法实现
```python
def dijkstra_sssp(Adj, w, s):
parent = {}
parent[s] = s
d = [math.inf] * len(Adj)
d[s] = 0
Q = PriorityQueue.build(Item(id=u, key=d[u]) for u in Adj)
while len(Q) > 0:
u = Q.delete_min().id
for v in Adj[u]:
if d[v] > d[u] + w(u,v):
d[v] = d[u] + w(u,v)
parent[v] = u
Q.decrease_key(id=v, new_key=d[v])
return d, parent
```
时间复杂度的计算方式与之前相同，但具体的数值取决于 PriorityQueue 的实现：
| Priority Queue | build | del\_min | dec\_key | Total |
| --------------- | ---------- | ------------ | -------- | ------------- |
| DAA Heap | $$V$$ | $$V$$ | 1 | $$V^2$$ |
| Hash Table Heap | $$V$$ ex. | $$V$$ ex. | 1 ex. | $$V^2$$ ex. |
| Binary Heap | $$V$$ | $$logV$$ | $$logV$$ | $$(V+E)logV$$ |
| Fibonacci Heap | $$V$$ | $$logV$$ am. | 1 am. | $$E+VlogV$$ |
* Fibonacci Heap Asymptotically 优于其它三种 Heap
* 在实践中，通常 Binary Heaps 要更快一些
#### Dijkstra 算法证明
略，请参考 course note。证明围绕 loop invariant 展开:
* For each node $$u \in{B}$$ ， $$d\[u] = \delta(s,u)$$
* For each node $$v \notin{B}$$ ，its key $$d\[u]$$ in Q equals the minimum weight of an s-v path that only visits nodes in B except for v
其中 B 为 bound。
#### Single Pair Search: Compute a single δ(s,t)
具体参考 course note。核心思想：从 s, t 同时运行 Dijkstra's Algorithm。当二者的边界出现交集时，从交集中找到最短路径。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/weighted-shortest-paths.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.