open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • 引言
  • 最短路径问题(Shortest-paths Problems)
  • 有向无环图中的单起点最短路径问题(DAG-SSSP)
  • 有环图的单起点最短路径问题
  • 无负权重边的单起点最短路径问题
  1. MIT - 6.006

Weighted Shortest Paths

引言

在进入 Weighted Shortest Paths 问题之前,先回忆一下 Unweighted Shortest Paths 问题,事实上,后者可以理解为前者的一个特例 --- 每条边的权重为相同的正数。

最短路径问题(Shortest-paths Problems)

最短路径问题实际上由一组相互关联的问题组成:

  • single-pair:找到图中两点之间的最短路径:δ(s,t)δ(s, t)δ(s,t)

  • single-source:找到从图中某一点 s 出发到达图中所有其它点的最短路径,δ(s,t)δ(s, t)δ(s,t) for all v∈Vv \in{V}v∈V ;即以 s 为根节点的最短路径树(shortest-path tree)。

  • all-pairs:找到图中任意两点的最短路径:δ(s,t)δ(s, t)δ(s,t) for all u,v∈Vu, v \in{V}u,v∈V

权重

即使图中的两点之间存在路径,这两点之间也可能不存在最短路径!--- 图中存在负权重环(negative-weight cycle)

现实意义

最短路径问题是极具现实意义的问题:

  • 地图导航

  • 网络路由

大多数现实问题中,不同路径的成本通常不同,因此可以被抽象为 Weighted-shortest-paths Problems。

特点

  • Subpath Property:最短路径的任意子路径也是最短路径(如何证明?)

  • Tree Property:从图中某点 s 出发到达图中其它所有可达点的路径恰好组成以 s 为根节点的树 T

算法框架

  1. 初始化: d={s:0,rest:∞}d = \{ s: 0, rest: ∞ \}d={s:0,rest:∞} , parent={s:s}parent = \{s: s\}parent={s:s}

  2. 选择一条边 (u,v)∈E(u, v) \in{E}(u,v)∈E

  3. relax (u,v)(u, v)(u,v) (具体见下文)

  4. 重复步骤 2, 3 直到没有 relaxation 发生为止

Relaxation

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)(u, v)(u,v) maintains invariant d[v]⩾δ(s,v)d[v] \geqslant δ(s, v)d[v]⩾δ(s,v)

  2. Termination Lemma: if no edge can be relaxed, then d[v]=δ(s,v)d[v] = δ(s, v)d[v]=δ(s,v) for all v∈Vv \in {V}v∈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 将面临更大的挑战,可能存在 δ(s,v)=−∞\delta(s, v) = -∞δ(s,v)=−∞ 的情况,这种情况下,我们希望算法如何输出?

  • 版本1:检测出是否有负权重环,如果存在则认为输入错误

  • 版本2:找到所有满足 δ(s,v)=−∞\delta(s, v) = -∞δ(s,v)=−∞ 的节点

  • 版本3:找到其中一个负权重环

Bellmand-Ford 算法实现很简单,重复 ∣V∣−1|V| - 1∣V∣−1 轮 relaxation 操作,每轮都遍历并 relax 图上的所有边:

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∣×∣E∣)O(|V|\times|E|)O(∣V∣×∣E∣)

仔细推算,实际上是 O(∣V∣∣E∣+∣V∣2)O(|V||E| + |V|^2)O(∣V∣∣E∣+∣V∣2)

版本1:检测负权重环是否存在

完成 ∣V∣−1|V|-1∣V∣−1 轮 relaxation 操作后,检测任何边是否仍然可以 relax,如果可以,就判断存在负权重环:

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∣ 轮应当找到节点数为 ∣V∣|V| ∣V∣ 的最短路径,但不出现重复点的最短路径最多只能包含 ∣V∣−1|V|-1∣V∣−1 个节点。

时间复杂度:

最后检测操作复杂度为 O(∣E∣)O(|E|)O(∣E∣) ,总体仍然为 O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)

版本2:找到所有 δ(s,v)=−∞\delta(s, v) = -∞δ(s,v)=−∞ 的节点

完成 ∣V∣−1|V|-1∣V∣−1 轮 relaxation 操作后,搜集所有可以 relax 的节点组成集合 N,N = { v | some edge (u, v) is relaxable} ,所有从 N 中的节点出发能到达的节点最短路径都为 −∞-∞−∞

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∣)O(|V||E|)O(∣V∣∣E∣)。Dijkstra 算法能实现 O(∣E∣+∣V∣log∣V∣)O(|E| + |V|log|V|)O(∣E∣+∣V∣log∣V∣) 的时间复杂度。

Dijkstra 的核心思想

从起点出发,向外有选择地拓宽边界,同时保证

  • 在边界内的点都已经找到了最短路径

  • 在边界外的点都已经找到只经过边界内的点可达的最短路径

Srini Devadas 在课堂上给出的 demo 非常震撼:如图 2 所示:他将一个图具象化为用线相连的球,线的长短表示图中边缘的权重,然后提起其中一只球 A,由于重力的原因,离球 A 最近的球 B 会先到达最低点,同时它们之间的线处于紧绷状态,而离球 A 第二近的球 C 会第二个到达最低点,它的最短路径上的线也会处于紧绷状态,如图 3 所示。如果用慢镜头来看,将可以看到每个球按顺序陆续达到最低点,及边界范围逐渐扩大的过程。用物理来解释算法,非常震撼!

Dijkstra 算法实现

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

1

Hash Table Heap

1 ex.

Binary Heap

Fibonacci Heap

1 am.

  • Fibonacci Heap Asymptotically 优于其它三种 Heap

  • 在实践中,通常 Binary Heaps 要更快一些

Dijkstra 算法证明

略,请参考 course note。证明围绕 loop invariant 展开:

  • For each node u∈Bu \in{B}u∈B , d[u]=δ(s,u)d[u] = \delta(s,u)d[u]=δ(s,u)

  • For each node v∉Bv \notin{B}v∈/B ,its key d[u]d[u]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。当二者的边界出现交集时,从交集中找到最短路径。

PreviousTree & SearchNextString Matching, Karp-Rabin

Last updated 6 years ago

ex.

ex.

ex.

am.

VVV
VVV
V2V^2V2
VVV
VVV
V2V^2V2
VVV
logVlogVlogV
logVlogVlogV
(V+E)logV(V+E)logV(V+E)logV
VVV
logVlogVlogV
E+VlogVE+VlogVE+VlogV
图 1 - exponential growth in DAG
图 2 - Dijkstra's Algorithm Demo Setup
图 3 - Dijkstra's Algorithm Demo Show