# 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 所示：

![图 1 - exponential growth in DAG](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LSShqm8E3lu8tsUTH-O%2F-LSSjjN5ywEXEpCW6Anj%2FScreen%20Shot%202018-11-29%20at%2012.33.58%20PM.jpg?alt=media\&token=3c083d9b-3bc5-4f1f-9381-3a4ed889b7a4)

因此各种最短路径算法实际是在尝试减少 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 所示。如果用慢镜头来看，将可以看到每个球按顺序陆续达到最低点，及边界范围逐渐扩大的过程。用物理来解释算法，非常震撼！

<br>

![图 2 - Dijkstra's Algorithm Demo Setup](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LTSfGtkYZnM_06N_qV2%2F-LTSosu-urLY_JOGadRi%2FScreen%20Shot%202018-12-11%20at%2011.11.28%20PM.jpg?alt=media\&token=83833fe8-3c4d-415a-abba-25dc7a3d2df4)

![图 3 - Dijkstra's Algorithm Demo Show](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LTSfGtkYZnM_06N_qV2%2F-LTSp5KhCW_XU29tvUTf%2FScreen%20Shot%202018-12-11%20at%2011.12.12%20PM.jpg?alt=media\&token=da9522c5-adf4-4672-ae52-a0bbeeaf4011)

#### 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)$$&#x20;
* 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。当二者的边界出现交集时，从交集中找到最短路径。