第17章最短路径算法

学习目标

掌握单源最短路径问题的形式化定义
理解Dijkstra算法的正确性证明与复杂度分析
掌握Bellman-Ford算法处理负权边与负环检测
理解Floyd-Warshall算法的动态规划原理
掌握最短路径算法的应用场景与选择策略

17.1 最短路径问题形式化

17.1.1 问题定义

定义 17.1（带权图） 带权图 $G = (V, E, w)$ 由顶点集 $V$、边集 $E$ 和权重函数 $w: E \rightarrow \mathbb{R}$ 组成。

定义 17.2（路径权重） 路径 $P = (v_0, v_1, \ldots, v_k)$ 的权重定义为：

$$w(P) = \sum_{i=1}^{k} w(v_{i-1}, v_i)$$

定义 17.3（最短路径） 从顶点 $u$ 到顶点 $v$ 的最短路径是所有 $u$-$v$ 路径中权重最小的路径。最短距离定义为：

$$\delta(u, v) = \begin{cases} \min{w(P) : P \text{ 是 } u\text{-}v \text{ 路径}} & \text{若存在路径} \ \infty & \text{否则} \end{cases}$$

定义 17.4（单源最短路径问题） 给定带权图 $G = (V, E, w)$ 和源点 $s \in V$，求从 $s$ 到所有 $v \in V$ 的最短距离 $\delta(s, v)$。

定义 17.5（全源最短路径问题） 给定带权图 $G = (V, E, w)$，求所有顶点对 $(u, v)$ 的最短距离 $\delta(u, v)$。

17.1.2 最短路径的性质

定理 17.1（最优子结构） 若 $P = (v_0, v_1, \ldots, v_k)$ 是从 $v_0$ 到 $v_k$ 的最短路径，则对于任意 $0 \leq i \leq j \leq k$，子路径 $P' = (v_i, v_{i+1}, \ldots, v_j)$ 是从 $v_i$ 到 $v_j$ 的最短路径。

证明：反证法。若存在更短的 $v_i$-$v_j$ 路径 $P''$，则用 $P''$ 替换 $P$ 中的对应子路径，得到更短的 $v_0$-$v_k$ 路径，矛盾。 ∎

定理 17.2（三角不等式） 对于任意顶点 $u, v, w$：

$$\delta(u, w) \leq \delta(u, v) + \delta(v, w)$$

证明：若 $u$ 到 $w$ 不可达，右边为 $\infty$，不等式成立。否则，从 $u$ 到 $v$ 的最短路径加上从 $v$ 到 $w$ 的最短路径构成一条 $u$-$w$ 路径，其权重不小于最短距离。 ∎

定义 17.6（负环） 若图中存在环 $C$ 使得 $w(C) < 0$，则称 $C$ 为负环。

定理 17.3 若图中存在从源点 $s$ 可达的负环，则不存在有限的最短路径。

证明：设负环 $C$ 从 $s$ 可达，路径 $P$ 从 $s$ 到 $C$ 上某点。绕 $C$ 走 $k$ 圈后到达目标 $v$，路径权重为 $w(P) + k \cdot w(C)$。当 $k \to \infty$ 时，权重趋向 $-\infty$。 ∎

17.2 Dijkstra算法

17.2.1 算法描述

算法 17.1（Dijkstra）

Dijkstra(G, w, s):
    Initialize-Single-Source(G, s)
    S = ∅
    Q = G.V
    while Q ≠ ∅:
        u = Extract-Min(Q)
        S = S ∪ {u}
        for each vertex v ∈ G.Adj[u]:
            Relax(u, v, w)

Initialize-Single-Source(G, s):
    for each vertex v ∈ G.V:
        v.d = ∞
        v.π = NIL
    s.d = 0

Relax(u, v, w):
    if v.d > u.d + w(u, v):
        v.d = u.d + w(u, v)
        v.π = u

17.2.2 正确性证明

引理 17.1（初始化） 初始化后，对所有 $v \in V$：$v.d \geq \delta(s, v)$。

证明：$s.d = 0 = \delta(s, s)$。其他 $v.d = \infty \geq \delta(s, v)$。 ∎

引理 17.2（松弛保持） 若松弛前 $v.d \geq \delta(s, v)$，则松弛后仍成立。

证明：松弛操作设置 $v.d = u.d + w(u, v)$。由归纳假设 $u.d \geq \delta(s, u)$，故：

$$v.d = u.d + w(u, v) \geq \delta(s, u) + w(u, v) \geq \delta(s, v)$$

最后一个不等式由三角不等式得出。 ∎

引理 17.3（上界性质） 在算法执行过程中，对所有 $v \in V$：$v.d \geq \delta(s, v)$。

证明：由引理17.1和17.2，归纳得证。 ∎

引理 17.4（收敛性质） 若 $s \leadsto u \to v$ 是最短路径，且在松弛 $(u, v)$ 前有 $u.d = \delta(s, u)$，则松弛后 $v.d = \delta(s, v)$。

证明：松弛时：

$$v.d \leq u.d + w(u, v) = \delta(s, u) + w(u, v) = \delta(s, v)$$

由引理17.3，$v.d \geq \delta(s, v)$，故 $v.d = \delta(s, v)$。 ∎

定理 17.4（Dijkstra正确性） 对于非负权重的带权图 $G = (V, E, w)$，Dijkstra算法终止时，对所有 $v \in V$：$v.d = \delta(s, v)$。

证明：对加入 $S$ 的顶点数归纳。设 $u$ 是下一个加入 $S$ 的顶点，需证明 $u.d = \delta(s, u)$。

由引理17.3，$u.d \geq \delta(s, u)$。需证 $u.d \leq \delta(s, u)$。

设 $P$ 是从 $s$ 到 $u$ 的最短路径，$y$ 是 $P$ 上第一个不在 $S$ 中的顶点，$x$ 是 $y$ 在 $P$ 上的前驱（$x \in S$）。

当 $x$ 加入 $S$ 时，边 $(x, y)$ 被松弛。由归纳假设 $x.d = \delta(s, x)$，由引理17.4：

$$y.d = \delta(s, y) \leq \delta(s, u)$$

由于 $u$ 是 $Q$ 中 $d$ 值最小的顶点，$u.d \leq y.d \leq \delta(s, u)$。

因此 $u.d = \delta(s, u)$。 ∎

17.2.3 复杂度分析

定理 17.5（Dijkstra复杂度） 使用二叉堆的Dijkstra算法时间复杂度为 $O((|V| + |E|) \log |V|)$。

证明：

初始化：$O(|V|)$
Extract-Min：$|V|$ 次，每次 $O(\log |V|)$，共 $O(|V| \log |V|)$
Decrease-Key：最多 $|E|$ 次，每次 $O(\log |V|)$，共 $O(|E| \log |V|)$

总计 $O((|V| + |E|) \log |V|)$。 ∎

定理 17.6 使用斐波那契堆的Dijkstra算法时间复杂度为 $O(|E| + |V| \log |V|)$。

17.2.4 Python实现

python

import heapq
from typing import Dict, List, Tuple, Optional, Set
import math

V = TypeVar('V')

def dijkstra(g: WeightedGraph[V, float], source: V) -> Tuple[Dict[V, float], Dict[V, Optional[V]]]:
    distance: Dict[V, float] = {v: math.inf for v in g.vertices()}
    parent: Dict[V, Optional[V]] = {v: None for v in g.vertices()}
    distance[source] = 0
    
    pq: List[Tuple[float, V]] = [(0, source)]
    visited: Set[V] = set()
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if u in visited:
            continue
        visited.add(u)
        
        for v in g.neighbors(u):
            if v in visited:
                continue
            weight = g.get_weight(u, v)
            if weight is None:
                continue
            
            new_dist = distance[u] + weight
            if new_dist < distance[v]:
                distance[v] = new_dist
                parent[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return distance, parent

def dijkstra_path(g: WeightedGraph[V, float], source: V, target: V) -> Optional[Tuple[List[V], float]]:
    distance, parent = dijkstra(g, source)
    
    if distance[target] == math.inf:
        return None
    
    path: List[V] = []
    current: Optional[V] = target
    while current is not None:
        path.append(current)
        current = parent[current]
    
    return path[::-1], distance[target]

class Dijkstra:
    def __init__(self, g: WeightedGraph[V, float]):
        self.g = g
    
    def run(self, source: V) -> Tuple[Dict[V, float], Dict[V, Optional[V]]]:
        return dijkstra(self.g, source)
    
    def shortest_path(self, source: V, target: V) -> Optional[Tuple[List[V], float]]:
        return dijkstra_path(self.g, source, target)
    
    def is_reachable(self, source: V, target: V) -> bool:
        distance, _ = dijkstra(self.g, source)
        return distance[target] < math.inf

17.3 Bellman-Ford算法

17.3.1 算法描述

算法 17.2（Bellman-Ford）

Bellman-Ford(G, w, s):
    Initialize-Single-Source(G, s)
    for i = 1 to |G.V| - 1:
        for each edge (u, v) ∈ G.E:
            Relax(u, v, w)
    for each edge (u, v) ∈ G.E:
        if v.d > u.d + w(u, v):
            return FALSE
    return TRUE

17.3.2 正确性证明

引理 17.5 设 $P = (v_0, v_1, \ldots, v_k)$ 是从 $s$ 到 $v_k$ 的最短路径，其中 $v_0 = s$。在第 $i$ 轮迭代后，$v_i.d = \delta(s, v_i)$。

证明：对 $i$ 归纳。$i=0$：$v_0 = s$，$s.d = 0 = \delta(s, s)$。

设第 $i-1$ 轮后 $v_{i-1}.d = \delta(s, v_{i-1})$。在第 $i$ 轮，边 $(v_{i-1}, v_i)$ 被松弛：

$$v_i.d \leq v_{i-1}.d + w(v_{i-1}, v_i) = \delta(s, v_{i-1}) + w(v_{i-1}, v_i) = \delta(s, v_i)$$

由引理17.3，$v_i.d \geq \delta(s, v_i)$，故 $v_i.d = \delta(s, v_i)$。 ∎

定理 17.7（Bellman-Ford正确性） 若图中不存在从 $s$ 可达的负环，则Bellman-Ford算法返回TRUE，且对所有 $v$：$v.d = \delta(s, v)$。

证明：设 $v$ 从 $s$ 可达，最短路径 $P$ 有 $k \leq |V| - 1$ 条边。由引理17.5，第 $k$ 轮后 $v.d = \delta(s, v)$。

若无负环，检查阶段不会发现违反松弛条件的边，返回TRUE。 ∎

定理 17.8（负环检测） Bellman-Ford算法返回FALSE当且仅当存在从 $s$ 可达的负环。

证明：（$\Leftarrow$）若有负环 $C$ 从 $s$ 可达，绕 $C$ 一圈可继续减小距离，检查阶段发现违反条件。

（$\Rightarrow$）若返回FALSE，存在边 $(u, v)$ 使得 $v.d > u.d + w(u, v)$。这意味着 $u.d < \infty$，即 $u$ 从 $s$ 可达。若无边权为负，经过 $|V|-1$ 轮后所有最短路径已找到。违反条件意味着存在负环。 ∎

17.3.3 复杂度分析

定理 17.9 Bellman-Ford算法时间复杂度为 $O(|V| \cdot |E|)$。

证明：

初始化：$O(|V|)$
主循环：$|V|-1$ 轮，每轮遍历所有边 $O(|E|)$
检查阶段：$O(|E|)$

总计 $O(|V| \cdot |E|)$。 ∎

17.3.4 Python实现

python

from typing import Dict, List, Tuple, Optional, Set
import math

def bellman_ford(g: WeightedGraph[V, float], source: V) -> Tuple[bool, Dict[V, float], Dict[V, Optional[V]]]:
    distance: Dict[V, float] = {v: math.inf for v in g.vertices()}
    parent: Dict[V, Optional[V]] = {v: None for v in g.vertices()}
    distance[source] = 0
    
    vertices = list(g.vertices())
    edges = list(g.edges_with_weights())
    
    for _ in range(len(vertices) - 1):
        relaxed = False
        for edge in edges:
            u, v, w = edge.source, edge.target, edge.weight
            if distance[u] != math.inf and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                parent[v] = u
                relaxed = True
        if not relaxed:
            break
    
    for edge in edges:
        u, v, w = edge.source, edge.target, edge.weight
        if distance[u] != math.inf and distance[u] + w < distance[v]:
            return False, distance, parent
    
    return True, distance, parent

def find_negative_cycle(g: WeightedGraph[V, float], source: V) -> Optional[List[V]]:
    distance: Dict[V, float] = {v: math.inf for v in g.vertices()}
    parent: Dict[V, Optional[V]] = {v: None for v in g.vertices()}
    distance[source] = 0
    
    vertices = list(g.vertices())
    edges = list(g.edges_with_weights())
    last_relaxed = None
    
    for _ in range(len(vertices)):
        last_relaxed = None
        for edge in edges:
            u, v, w = edge.source, edge.target, edge.weight
            if distance[u] != math.inf and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                parent[v] = u
                last_relaxed = v
    
    if last_relaxed is None:
        return None
    
    for _ in range(len(vertices)):
        last_relaxed = parent[last_relaxed]
    
    cycle: List[V] = []
    current = last_relaxed
    while True:
        cycle.append(current)
        current = parent[current]
        if current == last_relaxed:
            break
    
    return cycle[::-1]

class BellmanFord:
    def __init__(self, g: WeightedGraph[V, float]):
        self.g = g
    
    def run(self, source: V) -> Tuple[bool, Dict[V, float], Dict[V, Optional[V]]]:
        return bellman_ford(self.g, source)
    
    def has_negative_cycle(self, source: V) -> bool:
        success, _, _ = bellman_ford(self.g, source)
        return not success
    
    def find_negative_cycle(self, source: V) -> Optional[List[V]]:
        return find_negative_cycle(self.g, source)

17.4 Floyd-Warshall算法

17.4.1 动态规划原理

定义 17.7 设 $d_{ij}^{(k)}$ 为从 $i$ 到 $j$ 且中间顶点仅限于 ${1, 2, \ldots, k}$ 的最短路径长度。

递推关系：

$$d_{ij}^{(k)} = \begin{cases} w_{ij} & k = 0 \ \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}) & k \geq 1 \end{cases}$$

定理 17.10 上述递推关系正确计算最短路径。

证明：对于 $d_{ij}^{(k)}$，最短路径要么不经过 $k$（值为 $d_{ij}^{(k-1)}$），要么经过 $k$（值为 $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$）。由最优子结构，取最小值。 ∎

17.4.2 算法描述

算法 17.3（Floyd-Warshall）

Floyd-Warshall(W):
    n = W.rows
    D^(0) = W
    for k = 1 to n:
        for i = 1 to n:
            for j = 1 to n:
                d_{ij}^{(k)} = min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)})
    return D^(n)

17.4.3 正确性证明

定理 17.11 Floyd-Warshall算法正确计算所有顶点对的最短距离。

证明：对 $k$ 归纳。$k=0$ 时，$d_{ij}^{(0)} = w_{ij}$，即直接边的权重。设对 $k-1$ 成立，则 $d_{ij}^{(k)}$ 正确计算了中间顶点限于 ${1, \ldots, k}$ 的最短路径。当 $k = n$ 时，所有顶点都可作为中间点，得到真正的最短路径。 ∎

17.4.4 复杂度分析

定理 17.12 Floyd-Warshall算法时间复杂度为 $O(|V|^3)$，空间复杂度为 $O(|V|^2)$。

证明：三重循环，每重 $|V|$ 次，共 $O(|V|^3)$。距离矩阵 $O(|V|^2)$。 ∎

17.4.5 Python实现

python

from typing import Dict, List, Tuple, Optional
import math

def floyd_warshall(g: WeightedGraph[V, float]) -> Tuple[Dict[Tuple[V, V], float], Dict[Tuple[V, V], Optional[V]]]:
    vertices = list(g.vertices())
    n = len(vertices)
    idx = {v: i for i, v in enumerate(vertices)}
    
    dist = [[math.inf] * n for _ in range(n)]
    next_vertex = [[None] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
        next_vertex[i][i] = vertices[i]
    
    for edge in g.edges_with_weights():
        u, v, w = edge.source, edge.target, edge.weight
        i, j = idx[u], idx[v]
        dist[i][j] = w
        next_vertex[i][j] = v
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != math.inf and dist[k][j] != math.inf:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_vertex[i][j] = next_vertex[i][k]
    
    distance: Dict[Tuple[V, V], float] = {}
    predecessor: Dict[Tuple[V, V], Optional[V]] = {}
    
    for i in range(n):
        for j in range(n):
            distance[(vertices[i], vertices[j])] = dist[i][j]
            predecessor[(vertices[i], vertices[j])] = next_vertex[i][j]
    
    return distance, predecessor

def reconstruct_path(predecessor: Dict[Tuple[V, V], Optional[V]], source: V, target: V) -> Optional[List[V]]:
    if predecessor.get((source, target)) is None:
        return None if source != target else [source]
    
    path = [source]
    current = source
    while current != target:
        current = predecessor[(current, target)]
        if current is None:
            return None
        path.append(current)
    
    return path

def has_negative_cycle_floyd(g: WeightedGraph[V, float]) -> bool:
    vertices = list(g.vertices())
    n = len(vertices)
    idx = {v: i for i, v in enumerate(vertices)}
    
    dist = [[math.inf] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    
    for edge in g.edges_with_weights():
        u, v, w = edge.source, edge.target, edge.weight
        i, j = idx[u], idx[v]
        dist[i][j] = min(dist[i][j], w)
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != math.inf and dist[k][j] != math.inf:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    for i in range(n):
        if dist[i][i] < 0:
            return True
    
    return False

class FloydWarshall:
    def __init__(self, g: WeightedGraph[V, float]):
        self.g = g
        self._distance: Optional[Dict[Tuple[V, V], float]] = None
        self._predecessor: Optional[Dict[Tuple[V, V], Optional[V]]] = None
    
    def run(self) -> Tuple[Dict[Tuple[V, V], float], Dict[Tuple[V, V], Optional[V]]]:
        if self._distance is None:
            self._distance, self._predecessor = floyd_warshall(self.g)
        return self._distance, self._predecessor
    
    def get_distance(self, u: V, v: V) -> float:
        distance, _ = self.run()
        return distance.get((u, v), math.inf)
    
    def get_path(self, source: V, target: V) -> Optional[List[V]]:
        _, predecessor = self.run()
        return reconstruct_path(predecessor, source, target)
    
    def has_negative_cycle(self) -> bool:
        return has_negative_cycle_floyd(self.g)

17.5 算法比较与选择

17.5.1 复杂度对比

算法	时间复杂度	适用场景
Dijkstra（二叉堆）	$O((V+E)\log V)$	非负权重，单源
Dijkstra（斐波那契堆）	$O(E + V\log V)$	非负权重，单源，稀疏图
Bellman-Ford	$O(VE)$	负权重，单源，负环检测
Floyd-Warshall	$O(V^3)$	全源最短路径
SPFA	$O(kE)$ 平均	负权重，单源

17.5.2 选择策略

定理 17.13（算法选择）

若仅需单源最短路径且无非负权重，选择Dijkstra
若需处理负权重或检测负环，选择Bellman-Ford
若需全源最短路径，选择Floyd-Warshall
若图非常稀疏且需多次查询，考虑Johnson算法

17.6 Johnson算法

17.6.1 算法思想

Johnson算法结合Bellman-Ford和Dijkstra，实现 $O(VE\log V)$ 的全源最短路径。

定理 17.14（重新赋权） 若对每个顶点 $v$ 赋予高度 $h(v)$，定义新权重：

$$\hat{w}(u, v) = w(u, v) + h(u) - h(v)$$

则新权重下最短路径与原权重下相同，且若 $h$ 满足 $h(v) \leq h(u) + w(u, v)$，则 $\hat{w} \geq 0$。

证明：对于路径 $P = (v_0, v_1, \ldots, v_k)$：

$$\hat{w}(P) = \sum_{i=1}^{k} \hat{w}(v_{i-1}, v_i) = \sum_{i=1}^{k} (w(v_{i-1}, v_i) + h(v_{i-1}) - h(v_i)) = w(P) + h(v_0) - h(v_k)$$

路径权重差为常数，不影响最短路径。 ∎

17.6.2 算法步骤

添加虚拟顶点 $s$，对每个 $v$ 添加边 $(s, v)$ 权重为 $0$
对 $s$ 运行Bellman-Ford，得到 $h(v) = \delta(s, v)$
重新赋权：$\hat{w}(u, v) = w(u, v) + h(u) - h(v)$
对每个顶点运行Dijkstra
还原距离：$d(u, v) = \hat{d}(u, v) - h(u) + h(v)$

python

def johnson(g: WeightedGraph[V, float]) -> Dict[Tuple[V, V], float]:
    vertices = list(g.vertices())
    n = len(vertices)
    
    h: Dict[V, float] = {v: 0 for v in vertices}
    edges = list(g.edges_with_weights())
    
    for _ in range(n):
        for edge in edges:
            u, v, w = edge.source, edge.target, edge.weight
            if h[u] + w < h[v]:
                h[v] = h[u] + w
    
    for edge in edges:
        u, v, w = edge.source, edge.target, edge.weight
        if h[u] + w < h[v]:
            raise ValueError("Graph contains negative cycle")
    
    reweighted = WeightedGraph[V, float](directed=g.is_directed())
    for v in vertices:
        reweighted.add_vertex(v)
    
    for edge in edges:
        u, v, w = edge.source, edge.target, edge.weight
        new_weight = w + h[u] - h[v]
        reweighted.add_edge(u, v, new_weight)
    
    result: Dict[Tuple[V, V], float] = {}
    
    for source in vertices:
        dist, _ = dijkstra(reweighted, source)
        for target in vertices:
            if dist[target] < math.inf:
                result[(source, target)] = dist[target] - h[source] + h[target]
            else:
                result[(source, target)] = math.inf
    
    return result

17.7 本章小结

本章系统介绍了最短路径算法：

问题定义：单源与全源最短路径的形式化
Dijkstra算法：贪心策略，非负权重，$O((V+E)\log V)$
Bellman-Ford算法：动态规划，负权重，$O(VE)$
Floyd-Warshall算法：全源最短路径，$O(V^3)$
Johnson算法：结合两种方法的高效全源算法

参考文献

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.
Warshall, S. (1962). A theorem on boolean matrices. Journal of the ACM, 9(1), 11-12.
Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1), 1-13.

下一章：第18章最小生成树与拓扑排序

第17章 最短路径算法 ​

学习目标 ​

17.1 最短路径问题形式化 ​

17.1.1 问题定义 ​

17.1.2 最短路径的性质 ​

17.2 Dijkstra算法 ​

17.2.1 算法描述 ​

17.2.2 正确性证明 ​

17.2.3 复杂度分析 ​

17.2.4 Python实现 ​

17.3 Bellman-Ford算法 ​

17.3.1 算法描述 ​

17.3.2 正确性证明 ​

17.3.3 复杂度分析 ​

17.3.4 Python实现 ​

17.4 Floyd-Warshall算法 ​

17.4.1 动态规划原理 ​

17.4.2 算法描述 ​

17.4.3 正确性证明 ​

17.4.4 复杂度分析 ​

17.4.5 Python实现 ​

17.5 算法比较与选择 ​

17.5.1 复杂度对比 ​

17.5.2 选择策略 ​

17.6 Johnson算法 ​

17.6.1 算法思想 ​

17.6.2 算法步骤 ​

17.7 本章小结 ​

参考文献 ​

第17章最短路径算法

学习目标

17.1 最短路径问题形式化

17.1.1 问题定义

17.1.2 最短路径的性质

17.2 Dijkstra算法

17.2.1 算法描述

17.2.2 正确性证明

17.2.3 复杂度分析

17.2.4 Python实现

17.3 Bellman-Ford算法

17.3.1 算法描述

17.3.2 正确性证明

17.3.3 复杂度分析

17.3.4 Python实现

17.4 Floyd-Warshall算法

17.4.1 动态规划原理

17.4.2 算法描述

17.4.3 正确性证明

17.4.4 复杂度分析

17.4.5 Python实现

17.5 算法比较与选择

17.5.1 复杂度对比

17.5.2 选择策略

17.6 Johnson算法

17.6.1 算法思想

17.6.2 算法步骤

17.7 本章小结

参考文献