最短路径问题

最短路径问题是图论与网络优化中最基础、最经典的问题之一，广泛应用于交通规划、通信网络、物流配送等领域。本章系统介绍三种核心算法：Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法，并通过完整的手算案例和Python代码实现，帮助读者掌握最短路径问题的建模与求解方法。

问题定义

基本概念

给定一个带权图 \( G = (V, E) \)，其中 \( V \) 为顶点集合，\( E \) 为边集合，每条边 \( (u, v) \in E \) 都有一个权值 \( w(u, v) \) 表示从顶点 \( u \) 到顶点 \( v \) 的“距离“（或代价）。最短路径问题要求找到从源点 \( s \) 到目标点 \( t \) 的一条路径，使得路径上所有边权之和最小。

数学表述

设从顶点 \( s \) 到顶点 \( t \) 的路径为 \( P = (v_0, v_1, v_2, \ldots, v_k) \)，其中 \( v_0 = s \)，\( v_k = t \)，则路径长度为：

\[ d(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) \]

最短路径问题即求解：

\[ \delta(s, t) = \min_{P \in \mathcal{P}_{st}} d(P) \]

其中 \( \mathcal{P}_{st} \) 为从 \( s \) 到 \( t \) 的所有路径的集合。

问题分类

最优子结构性质

最短路径问题具有最优子结构性质：如果 \( P = (v_0, v_1, \ldots, v_k) \) 是从 \( v_0 \) 到 \( v_k \) 的一条最短路径，则对于任意 \( 0 \leq i \leq j \leq k \)，子路径 \( P_{ij} = (v_i, v_{i+1}, \ldots, v_j) \) 是从 \( v_i \) 到 \( v_j \) 的一条最短路径。这一性质是动态规划和贪心策略求解最短路径问题的理论基础。

负权边与负权环

• 负权边：边权 \( w(u,v) < 0 \) 的边。Dijkstra算法不能处理负权边，但Bellman-Ford算法可以。
• 负权环：路径上存在一个环，其边权之和为负值。若从源点可达负权环，则最短路径无定义（可以通过反复经过负权环使路径长度趋于 \( -\infty \)）。

Dijkstra算法

算法原理

Dijkstra算法是解决非负权图上单源最短路径问题的经典贪心算法，由荷兰计算机科学家Edsger W. Dijkstra于1959年提出。

其核心思想是：维护一个已确定最短路径的顶点集合 \( S \)，每次从未确定的顶点中选取距离源点最近的顶点 \( u \)，将其加入 \( S \)，并用 \( u \) 的出边对其邻接顶点进行松弛操作（relaxation）。

松弛操作的定义为：对于边 \( (u, v) \)，若 \( d[v] > d[u] + w(u, v) \)，则更新：

\[ d[v] \leftarrow d[u] + w(u, v) \]

算法步骤

输入：带权有向图 \( G = (V, E) \)，源点 \( s \)，权函数 \( w: E \to \mathbb{R}^+ \)

输出：从 \( s \) 到所有顶点的最短距离 \( d[v] \) 及前驱节点 \( \pi[v] \)

1. 初始化：令 \( d[s] = 0 \)，对所有 \( v \neq s \)，令 \( d[v] = \infty \)；令 \( \pi[v] = \text{NIL} \)；令 \( S = \emptyset \)，\( Q = V \)（优先队列）。

2. 循环：当 \( Q \neq \emptyset \) 时：

   • 从 \( Q \) 中取出 \( d \) 值最小的顶点 \( u \)；
   • 将 \( u \) 加入 \( S \)；
   • 对 \( u \) 的每个邻接顶点 \( v \)，执行松弛操作：
     • 若 \( d[u] + w(u, v) < d[v] \)，则 \( d[v] \leftarrow d[u] + w(u, v) \)，\( \pi[v] \leftarrow u \)。

3. 终止：当所有顶点都加入 \( S \) 后，\( d[v] \) 即为从 \( s \) 到 \( v \) 的最短距离。

正确性证明思路

Dijkstra算法的正确性基于以下不变量：每次将顶点 \( u \) 从优先队列中取出时，\( d[u] = \delta(s, u) \)。证明采用反证法：假设某次取出的顶点 \( u \) 满足 \( d[u] > \delta(s, u) \)，由于边权非负，从 \( s \) 到 \( u \) 的最短路径必然经过某个已在 \( S \) 中的顶点到某个不在 \( S \) 中的顶点的边，而该顶点的 \( d \) 值不会大于 \( d[u] \)，与 \( u \) 是 \( Q \) 中 \( d \) 值最小的顶点矛盾。

时间复杂度

对于稠密图（\( E = O(V^2) \)），使用数组实现效率最高；对于稀疏图（\( E = O(V) \)），使用二叉堆或斐波那契堆更优。

Bellman-Ford算法

算法原理

Bellman-Ford算法可以处理含有负权边的图，其核心思想是：对所有边进行 \( |V| - 1 \) 轮松弛操作。第 \( k \) 轮松弛后，算法保证所有经过不超过 \( k \) 条边的最短路径都已被正确计算。

算法步骤

输入：带权有向图 \( G = (V, E) \)，源点 \( s \)，权函数 \( w: E \to \mathbb{R} \)

输出：最短距离 \( d[v] \)，前驱节点 \( \pi[v] \)，以及是否存在负权环

1. 初始化：令 \( d[s] = 0 \)，对所有 \( v \neq s \)，令 \( d[v] = \infty \)；\( \pi[v] = \text{NIL} \)。

2. 松弛：重复 \( |V| - 1 \) 次：

   • 对图中的每条边 \( (u, v) \in E \)：
     • 若 \( d[u] + w(u, v) < d[v] \)，则 \( d[v] \leftarrow d[u] + w(u, v) \)，\( \pi[v] \leftarrow u \)。

3. 检测负权环：再进行一轮松弛，若仍有边可以被松弛，则图中存在从源点可达的负权环。

时间复杂度

\[ T(n) = O(V \cdot E) \]

相比Dijkstra算法，Bellman-Ford的时间复杂度较高，但它的优势在于能处理负权边并检测负权环。

优化：SPFA算法

SPFA（Shortest Path Faster Algorithm）是Bellman-Ford的队列优化版本，使用一个队列存储被松弛过的顶点，只对队列中的顶点进行松弛操作。平均时间复杂度为 \( O(kE) \)（\( k \) 为小常数），但最坏情况仍为 \( O(VE) \)。

Floyd-Warshall算法

算法原理

Floyd-Warshall算法解决全源最短路径问题，即求所有顶点对之间的最短路径。它基于动态规划思想，逐步考虑中间顶点的加入。

定义 \( d^{(k)}[i][j] \) 为从顶点 \( i \) 到顶点 \( j \)，中间只经过编号不超过 \( k \) 的顶点的最短路径长度。状态转移方程为：

\[ d^{(k)}[i][j] = \min\left( d^{(k-1)}[i][j],; d^{(k-1)}[i][k] + d^{(k-1)}[k][j] \right) \]

初始条件：

\[ d^{(0)}[i][j] = \begin{cases} 0 & i = j \ w(i,j) & (i,j) \in E \ \infty & \text{otherwise} \end{cases} \]

算法步骤

1. 初始化：构造距离矩阵 \( D^{(0)} \)，其中 \( d[i][j] = w(i,j) \)（若边存在），\( d[i][i] = 0 \)，其余为 \( \infty \)。

2. 三重循环：

   • 对 \( k = 1, 2, \ldots, n \)：
     • 对 \( i = 1, 2, \ldots, n \)：
       • 对 \( j = 1, 2, \ldots, n \)：
         • \( d[i][j] \leftarrow \min(d[i][j],; d[i][k] + d[k][j]) \)

3. 检测负权环：若最终 \( d[i][i] < 0 \) 对某个 \( i \) 成立，则存在负权环。

路径重构

为了记录最短路径，额外维护前驱矩阵 \( \pi[i][j] \)，更新规则为：

\[ \text{若 } d[i][k] + d[k][j] < d[i][j]，\text{则 } \pi[i][j] \leftarrow \pi[k][j] \]

时间与空间复杂度

• 时间复杂度：\( O(V^3) \)
• 空间复杂度：\( O(V^2) \)

Floyd-Warshall算法的优势在于实现简洁、能处理负权边，且常数因子小。

实际案例分析

案例背景

某物流公司需要规划从仓库（顶点A）到5个配送点（顶点B、C、D、E、F）的最短运输路线。各节点之间的距离（单位：公里）如下：

A --2-- B
A --4-- C
B --1-- C
B --7-- D
C --3-- D
C --5-- E
D --2-- F
E --1-- F

Dijkstra算法手算过程

源点：A

第1轮：取出A（d=0），松弛邻接顶点：

• \( d[B] = \min(\infty, 0+2) = 2 \)，前驱为A
• \( d[C] = \min(\infty, 0+4) = 4 \)，前驱为A

第2轮：取出B（d=2），松弛邻接顶点：

• \( d[C] = \min(4, 2+1) = 3 \)，前驱更新为B
• \( d[D] = \min(\infty, 2+7) = 9 \)，前驱为B

第3轮：取出C（d=3），松弛邻接顶点：

• \( d[D] = \min(9, 3+3) = 6 \)，前驱更新为C
• \( d[E] = \min(\infty, 3+5) = 8 \)，前驱为C

第4轮：取出D（d=6），松弛邻接顶点：

• \( d[F] = \min(\infty, 6+2) = 8 \)，前驱为D

第5轮：取出E（d=8），松弛邻接顶点：

• \( d[F] = \min(8, 8+1) = 8 \)，不更新

第6轮：取出F（d=8），算法结束。

最终结果

Floyd-Warshall手算过程（简化示例）

取子图 \( {A, B, C, D} \) 进行演示。初始距离矩阵：

\[ D^{(0)} = \begin{pmatrix} 0 & 2 & 4 & \infty \ 2 & 0 & 1 & 7 \ 4 & 1 & 0 & 3 \ \infty & 7 & 3 & 0 \end{pmatrix} \]

经过顶点A（\( k=1 \)）：无更新，\( D^{(1)} = D^{(0)} \)。

经过顶点B（\( k=2 \)）：

• \( d[A][C] = \min(4, 2+1) = 3 \)，\( d[A][D] = \min(\infty, 2+7) = 9 \)

\[ D^{(2)} = \begin{pmatrix} 0 & 2 & 3 & 9 \ 2 & 0 & 1 & 7 \ 3 & 1 & 0 & 3 \ 9 & 7 & 3 & 0 \end{pmatrix} \]

经过顶点C（\( k=3 \)）：

• \( d[A][D] = \min(9, 3+3) = 6 \)，\( d[B][D] = \min(7, 1+3) = 4 \)

\[ D^{(3)} = \begin{pmatrix} 0 & 2 & 3 & 6 \ 2 & 0 & 1 & 4 \ 3 & 1 & 0 & 3 \ 6 & 4 & 3 & 0 \end{pmatrix} \]

经过顶点D（\( k=4 \)）：无更新。最终 \( D^{(4)} = D^{(3)} \) 即为全源最短路径距离矩阵。

Python代码实现

手写Dijkstra算法

import heapq

def dijkstra(graph, source):
    """
    Dijkstra算法求单源最短路径
    参数:
        graph: 邻接表，格式为 {节点: [(邻接节点, 权重), ...]}
        source: 源点
    返回:
        dist: 最短距离字典
        prev: 前驱节点字典
    """
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    prev = {node: None for node in graph}
    pq = [(0, source)]
    visited = set()

    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, weight in graph[u]:
            if v not in visited and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    return dist, prev


def reconstruct_path(prev, source, target):
    """根据前驱节点重构路径"""
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = prev[current]
    path.reverse()
    return path if path[0] == source else []


# 构建案例中的图
graph = {
    'A': [('B', 2), ('C', 4)],
    'B': [('A', 2), ('C', 1), ('D', 7)],
    'C': [('A', 4), ('B', 1), ('D', 3), ('E', 5)],
    'D': [('B', 7), ('C', 3), ('F', 2)],
    'E': [('C', 5), ('F', 1)],
    'F': [('D', 2), ('E', 1)]
}

dist, prev = dijkstra(graph, 'A')
print("从A出发的最短距离：")
for node in sorted(dist):
    path = reconstruct_path(prev, 'A', node)
    print(f"  A -> {node}: 距离={dist[node]}, 路径={'->'.join(path)}")

手写Bellman-Ford算法

def bellman_ford(vertices, edges, source):
    """
    Bellman-Ford算法（支持负权边）
    参数:
        vertices: 顶点列表
        edges: 边列表 [(u, v, w), ...]
        source: 源点
    返回:
        dist, prev, has_negative_cycle
    """
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    prev = {v: None for v in vertices}

    n = len(vertices)
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                updated = True
        if not updated:
            break

    # 检测负权环
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break

    return dist, prev, has_negative_cycle


# 示例：含负权边的图
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    ('A', 'B', 4), ('A', 'C', 2), ('B', 'D', 3),
    ('C', 'B', -1), ('C', 'D', 5), ('D', 'E', 2), ('B', 'E', 4)
]

dist, prev, neg_cycle = bellman_ford(vertices, edges, 'A')
if neg_cycle:
    print("警告：图中存在负权环！")
else:
    print("Bellman-Ford算法结果：")
    for v in sorted(dist):
        print(f"  A -> {v}: 距离={dist[v]}")

手写Floyd-Warshall算法

def floyd_warshall(vertices, adj_matrix):
    """
    Floyd-Warshall算法求全源最短路径
    参数:
        vertices: 顶点列表
        adj_matrix: 邻接表 {节点: [(邻接节点, 权重), ...]}
    返回:
        dist: 距离矩阵
        next_node: 后继节点矩阵
    """
    dist = {i: {j: float('inf') for j in vertices} for i in vertices}
    next_node = {i: {j: None for j in vertices} for i in vertices}

    for i in vertices:
        dist[i][i] = 0
    for i in vertices:
        for j, w in adj_matrix.get(i, []):
            dist[i][j] = w
            next_node[i][j] = j

    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]

    return dist, next_node


def floyd_reconstruct_path(next_node, source, target):
    """根据后继节点矩阵重构路径"""
    if next_node[source][target] is None:
        return []
    path = [source]
    current = source
    while current != target:
        current = next_node[current][target]
        path.append(current)
    return path


# 求解
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
adj = {
    'A': [('B', 2), ('C', 4)],
    'B': [('A', 2), ('C', 1), ('D', 7)],
    'C': [('A', 4), ('B', 1), ('D', 3), ('E', 5)],
    'D': [('B', 7), ('C', 3), ('F', 2)],
    'E': [('C', 5), ('F', 1)],
    'F': [('D', 2), ('E', 1)]
}

dist, next_node = floyd_warshall(vertices, adj)
print("全源最短路径距离矩阵：")
for i in vertices:
    row = [f"{dist[i][j]:>4}" if dist[i][j] != float('inf') else " INF" for j in vertices]
    print(f"  {i}: {''.join(row)}")

使用NetworkX库实现

import networkx as nx

# 创建带权无向图
G = nx.Graph()
G.add_weighted_edges_from([
    ('A', 'B', 2), ('A', 'C', 4), ('B', 'C', 1),
    ('B', 'D', 7), ('C', 'D', 3), ('C', 'E', 5),
    ('D', 'F', 2), ('E', 'F', 1)
])

# Dijkstra单源最短路径
print("=== Dijkstra算法 ===")
dist_all = nx.single_source_dijkstra_path_length(G, 'A')
path_all = nx.single_source_dijkstra_path(G, 'A')
for node in sorted(G.nodes()):
    print(f"  A -> {node}: 距离={dist_all[node]}, 路径={'->'.join(path_all[node])}")

# Bellman-Ford（有向图，支持负权边）
print("\n=== Bellman-Ford算法 ===")
DG = nx.DiGraph()
DG.add_weighted_edges_from([
    ('A', 'B', 4), ('A', 'C', 2), ('B', 'D', 3),
    ('C', 'B', -1), ('C', 'D', 5), ('D', 'E', 2), ('B', 'E', 4)
])
dist_bf = nx.single_source_bellman_ford_path_length(DG, 'A')
for node in sorted(DG.nodes()):
    print(f"  A -> {node}: 距离={dist_bf[node]}")

# Floyd-Warshall全源最短路径
print("\n=== Floyd-Warshall算法 ===")
dist_fw = dict(nx.floyd_warshall(G))
nodes = sorted(G.nodes())
header = "     " + "".join(f"{v:>6}" for v in nodes)
print(header)
for i in nodes:
    row = "".join(f"{dist_fw[i][j]:>6.0f}" for j in nodes)
    print(f"  {i}  {row}")

三种算法对比

应用注意事项与局限性

建模注意事项

1. 图的构建：正确识别问题中的节点和边是建模的关键。节点可以是地点、状态、时间点等抽象概念；边权可以表示距离、时间、费用等。

2. 有向与无向：需根据实际问题判断是否使用有向图。例如单行道应建模为有向边，双向通行则建模为无向边。

3. 权值非负性：使用Dijkstra算法前必须确认所有边权非负。若存在负权边，应改用Bellman-Ford算法。

4. 大规模图的处理：当图的规模较大时（如百万级节点），应考虑使用A*算法、双向Dijkstra或分层图等优化方法。

数学建模竞赛中的应用技巧

1. 多目标优化转换：当路径选择涉及多个目标时，可通过加权线性组合将多目标转化为单目标：

\[ w’(u,v) = \alpha \cdot t(u,v) + \beta \cdot c(u,v) \]

其中 \( t(u,v) \) 为时间，\( c(u,v) \) 为费用，\( \alpha, \beta \) 为权重系数。

2. 时变网络：在交通网络中，边权可能随时间变化（如高峰期拥堵）。此时需要将时间维度融入图结构，构建时空网络模型。

3. 约束最短路径：实际问题常带有约束条件（如途经指定节点、路径长度不超过某值等）。可通过图的变换、拉格朗日松弛等方法处理。

4. 结合其他模型：最短路径常与其他优化问题结合出现，例如：

   • 车辆路径问题（VRP）：最短路径是子问题
   • 网络流问题：最短路径用于寻找增广路
   • 选址问题：最短路径用于计算服务半径

局限性

1. 边权限制：Dijkstra算法无法处理负权边，这在某些实际场景中可能成为限制。

2. 动态变化：标准最短路径算法假设图是静态的。若图结构或权值动态变化，需要使用动态最短路径算法。

3. 随机性：当边权具有随机性（如行程时间不确定）时，需要使用随机最短路径模型，考虑期望值或概率约束。

4. 规模瓶颈：Floyd-Warshall的 \( O(V^3) \) 复杂度限制了它只能处理中小规模的图（通常 \( V \leq 1000 \)）。对于大规模全源最短路径，可考虑Johnson算法（\( O(V^2 \log V + VE) \)）。

5. 路径唯一性：最短路径可能不唯一。在实际应用中，可能需要找出所有最短路径或次短路径，这增加了算法的复杂度。

实用建议

• 小规模全源问题（\( V \leq 500 \)）：优先使用Floyd-Warshall，实现简单且高效。
• 大规模非负权单源问题：使用带优先队列的Dijkstra算法。
• 含负权边的单源问题：使用Bellman-Ford或SPFA算法。
• 竞赛中时间紧张：优先使用NetworkX等成熟库，确保正确性后再考虑优化。
• 结果验证：建议使用两种不同方法求解并对比结果，确保计算无误。