最短路径算法 - 数据结构与算法-学习笔记-上海佼艾

一、最短路径问题概述

最短路径问题是图论中最经典的问题之一，其目标是在加权图中找到两个顶点之间的最短路径（即边权和最小的路径）。根据起点和终点的数量，最短路径问题可分为三类：单源最短路径（从一个源点到所有其他顶点的最短路径）、多源最短路径（多个源点到其他顶点的最短路径）以及全源最短路径（所有顶点对之间的最短路径）。

解决最短路径问题的核心算法有三种，分别适用于不同的图结构：Dijkstra算法适用于无负权边的单源最短路径问题；Bellman-Ford算法可以处理带负权边的图，还能检测负权环；Floyd-Warshall算法则可以一次计算出所有顶点对之间的最短路径。理解这三者的设计思想——贪心、动态规划、动态规划——是掌握图算法的关键。

前置知识：理解最短路径算法需要掌握图的基本表示方法（邻接矩阵、邻接表）、堆（优先队列）数据结构、动态规划的基本思想以及大O记号表示的时间复杂度分析。本文所有代码示例使用Python语言，专注于算法逻辑本身。

二、Dijkstra算法（单源正权图）

2.1 基本思想与原理

Dijkstra算法由计算机科学家Edsger W. Dijkstra于1956年提出，是解决非负权图单源最短路径问题的最经典算法。其核心思想是贪心策略：每次从未访问的顶点中选择距离源点最近的顶点，将其加入已确定最短路径的集合中，然后利用该顶点"松弛"其邻接顶点。

算法的正确性依赖于一个关键性质：在非负权图中，当前未访问顶点中距离源点最近的那个顶点，其最短路径已经确定，不可能再通过其他未被访问的顶点变得更短。这正是贪心选择性质的体现。通过反复执行"选择-松弛"操作，Dijkstra算法能够逐步确定所有顶点的最短路径。

2.2 朴素实现 —— O(V²)

在不使用任何数据结构优化时，Dijkstra算法每次需要O(V)的时间来寻找当前最近的顶点，总共执行V次，因此时间复杂度为O(V²)。适用于稠密图。

def dijkstra_naive(graph, start):
    # graph: 邻接矩阵表示, graph[u][v] 表示边u->v的权重, INF表示不连通
    n = len(graph)
    INF = float('inf')
    dist = [INF] * n        # 最短距离数组
    visited = [False] * n  # 是否已确定最短路径
    dist[start] = 0

    for _ in range(n):
        # 寻找未访问顶点中距离最小的
        u = -1
        min_dist = INF
        for v in range(n):
            if not visited[v] and dist[v] < min_dist:
                min_dist = dist[v]
                u = v

        if u == -1:  # 剩余顶点不可达
            break

        visited[u] = True

        # 松弛操作：用u更新邻接顶点
        for v in range(n):
            if not visited[v] and graph[u][v] != INF:
                new_dist = dist[u] + graph[u][v]
                if new_dist < dist[v]:
                    dist[v] = new_dist

    return dist

2.3 堆优化实现 —— O(E log V)

对于稀疏图，使用最小堆（优先队列）来维护当前最近的顶点，可以将寻找最近顶点的时间降低到O(log V)。核心思路是将(dist[v], v)二元组放入堆中，每次取出堆顶元素即为当前最近的顶点。由于每条边最多触发一次松弛，堆中最多包含E个元素，总时间复杂度为O((V+E) log V) = O(E log V)。

import heapq

def dijkstra_heap(graph, start):
    # graph: 邻接表, graph[u] = [(v1, w1), (v2, w2), ...]
    n = len(graph)
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0

    # 最小堆: (距离, 顶点)
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        # 如果取出的距离大于已记录的距离，跳过（懒删除）
        if d > dist[u]:
            continue

        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))

    return dist

2.4 局限性分析

Dijkstra算法不能处理负权边！当图中存在负权边时，贪心选择性质被破坏。一个已经确定最短路径的顶点，可能因为一条后续发现的负权边而获得更短的路径——Dijkstra的贪心策略不允许这种情况发生。例如，在图A→B(2)、A→C(1)、C→B(-3)中，Dijkstra会先确定C的距离为1，然后用C松弛B得到dist[B]=1+(-3)=-2，但实际上dist[A→B]却是2，已经错误地将A→B的距离确定为了2。

三、Bellman-Ford算法（单源含负权）

3.1 动态规划思想

Bellman-Ford算法由Richard Bellman和Lester Ford各自独立发明，采用动态规划思想解决单源最短路径问题。与Dijkstra的"短视"贪心不同，Bellman-Ford通过逐轮松弛来逼近最短路径：在第k轮迭代结束时，算法能够找到从源点到每个顶点不超过k条边的最短路径。

算法的核心观察是：在一个包含V个顶点的图中，任意最短路径至多包含V-1条边（假设不存在负权环）。因此，只需要对所有的边进行V-1轮松弛操作，就能保证找到所有顶点的最短路径。每一轮松弛都尝试用当前已知的dist[u] + w更新dist[v]。

3.2 算法实现 —— O(VE)

def bellman_ford(edges, n, start):
    # edges: 边列表 [(u, v, w), ...]
    # n: 顶点数
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0

    # 进行 V-1 轮松弛
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        # 优化：如果某一轮没有更新，提前结束
        if not updated:
            break

    return dist

3.3 负环检测

Bellman-Ford算法的一个独特优势是能够检测图中是否存在负权环（即环路上边权之和为负数的环）。如果图中存在从源点可达的负环，那么最短路径将不存在——我们可以沿着负环无限绕圈，使路径长度不断减小到负无穷。检测方法非常简单：在完成V-1轮松弛后，再对所有边执行第V次松弛。如果仍能更新某个顶点的最短距离，说明图中存在从源点可达的负权环。

def bellman_ford_detect_negative_cycle(edges, n, start):
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
    prev = [-1] * n  # 记录前驱顶点，用于路径重构

    # V-1 轮松弛
    for i in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    # 第 V 轮：检测负环
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None, True  # 存在负权环

    return dist, False

优化技巧：SPFA算法（Shortest Path Faster Algorithm）是Bellman-Ford的队列优化版本，利用队列代替全量遍历。在随机图中SPFA通常很快，但最坏时间复杂度仍为O(VE)。SPFA的核心是：只有被松弛过的顶点才可能触发后续松弛，因此可以用队列维护待松弛的顶点集合，避免每轮遍历所有边。

四、Floyd-Warshall算法（全源最短路径）

4.1 动态规划思想

Floyd-Warshall算法（又称Floyd算法）以极其简洁的三层循环解决了全源最短路径问题，时间复杂度为O(V³)。其核心是经典的动态规划递推：设dp[k][i][j]表示"允许使用编号不超过k的顶点作为中间节点"时，从i到j的最短路径长度。递推关系为：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

通俗地说，从i到j的最短路径要么不经过顶点k（保持原来的路径），要么经过顶点k（从i到k的最短路径加上从k到j的最短路径）。通过滚动数组优化，可以省略k维度，直接在原数组上迭代，即经典的Floyd-Warshall三层循环。

4.2 算法实现 —— O(V³)

def floyd_warshall(graph):
    # graph: 邻接矩阵, graph[i][j] = 边权, INF表示不连通
    n = len(graph)
    INF = float('inf')

    # 初始化距离矩阵
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != INF:
                dist[i][j] = graph[i][j]

    # 核心三层循环
    for k in range(n):          # 中间顶点
        for i in range(n):      # 起点
            for j in range(n):  # 终点
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j],
                                       dist[i][k] + dist[k][j])

    return dist

4.3 传递闭包

Floyd-Warshall算法的思想不仅用于求最短路径，还可以用于计算有向图的传递闭包（Transitive Closure），即判断图中任意两点之间是否存在路径。只需将距离比较改为逻辑比较即可：

def transitive_closure(graph):
    # graph: 邻接矩阵, graph[i][j] = True 表示存在边i->j
    n = len(graph)
    reach = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            reach[i][j] = graph[i][j]
        reach[i][i] = True  # 自身可达

    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

    return reach

Floyd算法的优点与局限：优点在于代码极简、易于实现、一次求解全源最短路径。局限在于时间复杂度固定为O(V³)，对于大规模图（V > 1000）性能急剧下降。空间复杂度为O(V²)存储距离矩阵，对于百万顶点级别的图不可行。此外，Floyd-Warshall算法可以正确处理负权边，但不能容忍负权环（检测方式与Bellman-Ford类似）。

五、路径重构（prev数组）

在实际应用中，我们不仅需要最短路径的长度，还需要最短路径本身（即经过哪些顶点）。路径重构的经典方法是在松弛过程中维护一个前驱数组prev[]（或后继数组），记录每个顶点在最短路径中的前一个顶点。

对于Dijkstra和Bellman-Ford，当通过顶点u"松弛"顶点v使得dist[v]被更新时，我们将prev[v]设置为u，表示最短路径中v的前驱是u。最终，从目标顶点t回溯到源点s，即可得到完整的路径。

def reconstruct_path(prev, start, target):
    """根据前驱数组重构从start到target的最短路径"""
    path = []
    curr = target
    while curr != -1:
        path.append(curr)
        curr = prev[curr]
    path.reverse()  # 反转得到从start到target的顺序
    if path[0] != start:
        return []  # 不存在路径
    return path

对于Floyd-Warshall算法，路径重构稍有不同。我们需要维护一个二维的后继矩阵next[][]（或前驱矩阵）。初始化时，如果存在边i→j，则next[i][j] = j。在核心循环中，如果发现经过k的路径更短，则更新next[i][j] = next[i][k]。

def floyd_with_path(graph):
    n = len(graph)
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    # next[i][j] 表示从i到j的最短路径中i的下一个顶点
    nxt = [[-1] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
                nxt[i][j] = j
            elif graph[i][j] != INF:
                dist[i][j] = graph[i][j]
                nxt[i][j] = j

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        nxt[i][j] = nxt[i][k]  # 路径变为 i→...→k→...→j

    def get_path(i, j):
        if nxt[i][j] == -1:
            return []
        path = [i]
        while i != j:
            i = nxt[i][j]
            path.append(i)
        return path

    return dist, get_path

路径重构的技巧：对于Dijkstra和Bellman-Ford，前驱数组的回溯时间复杂度为O(V)，相当于线性扫描路径长度。对于Floyd-Warshall，后继矩阵的查询时间复杂度也是O(V)。无论哪种算法，路径重构的额外空间开销都是O(V)或O(V²)，在大多数应用中可以接受。

六、算法对比总结

下表从多个维度对三种核心最短路径算法进行系统对比，帮助在实际问题中正确选型：

对比维度	Dijkstra	Bellman-Ford	Floyd-Warshall
核心思想	贪心 + 松弛	动态规划（逐轮松弛）	动态规划（区间递推）
时间复杂度	O(E log V) 堆优化 O(V²) 朴素	O(VE)	O(V³)
空间复杂度	O(V) / O(E + V)	O(V)	O(V²)
求解类型	单源	单源	全源
负权边	不支持	支持	支持
负环检测	不支持	支持	可检测（对角线为负）
适用图规模	大图（V > 10⁴, E > 10⁵）	中等图	小图（V ≤ 500）
代码复杂度	中等（需堆实现）	简单	极简
适用场景	导航、路由	金融、经济模型	传递闭包、稠密图

算法选型黄金法则：①无负权边且单源 → Dijkstra堆优化；②有负权边且单源 → Bellman-Ford/SPFA；③需要全源最短路径或传递闭包 → Floyd-Warshall（V<500时）；④需要检测负环 → Bellman-Ford。切勿在负权图上使用Dijkstra，会在面试和工程中同时犯错。

七、典型应用场景

7.1 导航系统中的路径规划

GPS导航需要实时计算从当前位置到目的地的最短路径。实际地图中的道路网络通常包含数百万个顶点和边，但道路权重（距离/时间）均为正值，因此Dijkstra算法及其变体（如A*算法）是导航系统的核心。堆优化的Dijkstra算法在大规模道路网络上的性能完全可以满足实时导航的需求。现代导航系统进一步引入了分层思想（Contraction Hierarchies），将Dijkstra的搜索空间压缩几个数量级。

7.2 计算机网络路由协议

在计算机网络中，OSPF（Open Shortest Path First）和IS-IS等路由协议的核心就是最短路径算法。OSPF使用Dijkstra算法计算路由表，每条链路的"代价"可以手动配置或根据带宽自动计算（都是正值）。而RIP（Routing Information Protocol）则使用Bellman-Ford算法的分布式版本，每台路由器仅与邻居交换距离向量——这正是Bellman-Ford"逐轮传播"思想的分布式体现。

7.3 社交网络中的"六度分隔"

在社交网络分析中，最短路径长度（即两个用户之间的"距离"）是衡量社交亲密度的基本指标。对于用户量达数十亿的社交平台，计算全源最短路径显然是不可行的。实际应用中常采用BFS（对于无权图求最短路径）或双向Dijkstra来快速估算两个用户之间的社交距离。而Floyd-Warshall算法可用于小规模子图（如社团内部）的全源距离分析。

7.4 金融风险传导分析

在金融网络中，银行之间的借贷关系可以建模为有向加权图。风险传染路径本质上就是最短路径问题，且由于债务关系可能存在负边权（如资产核销），此时必须使用Bellman-Ford算法来准确计算风险传导路径。更重要的是，负环检测能力可以识别金融系统中的循环套利或系统性风险传导链。

行业案例：Google Maps早期使用Dijkstra算法作为路径规划基础；OpenStreetMap的路由引擎OSRM基于Dijkstra的分层优化实现亚毫秒级查询；交通领域的实时ETC（预计到达时间）计算同样依赖最短路径算法家族。

八、进阶扩展

8.1 有向无环图（DAG）上的最短路径

如果输入图是一个DAG，我们可以利用拓扑排序在O(V+E)时间内解决单源最短路径问题，这比Dijkstra和Bellman-Ford更快。具体做法是：先对DAG进行拓扑排序，然后按拓扑序依次处理每个顶点，松弛其出边。由于拓扑序保证了所有前驱顶点在当前顶点之前被处理，因此每个顶点在第一次访问时就已经获得了正确的最短路径，无需多轮迭代。

def dag_shortest_path(graph, n, start):
    # 1. 拓扑排序（Kahn算法）
    in_degree = [0] * n
    for u in range(n):
        for v, w in graph[u]:
            in_degree[v] += 1

    queue = [i for i in range(n) if in_degree[i] == 0]
    topo = []
    while queue:
        u = queue.pop(0)
        topo.append(u)
        for v, w in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    # 2. 按拓扑序松弛
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0
    for u in topo:
        if dist[u] != INF:
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    return dist

8.2 双向搜索与A*算法

当只需求解一对顶点之间的最短路径时，双向Dijkstra可以显著减少搜索空间。同时从起点和终点执行Dijkstra，当两个搜索方向相遇时即可停止。在随机图中，双向Dijkstra的搜索空间大约是单向的平方根，效率提升显著。进一步地，A*算法引入启发式函数引导搜索方向，在导航系统中广泛使用。

8.3 Johnson算法

Johnson算法是将Bellman-Ford和Dijkstra结合的全源最短路径算法。先用Bellman-Ford对图进行重赋权（reweighting），消除负权边但保持最短路径不变；然后对每个顶点运行一次Dijkstra堆优化。对于稀疏图，Johnson算法的时间复杂度为O(VE + V² log V)，优于Floyd-Warshall的O(V³)。

九、核心要点总结

最短路径算法知识框架：

Dijkstra —— 贪心思想，堆优化O(E log V)，适用于非负权图单源最短路径，是实际应用中最常用的最短路径算法
Bellman-Ford —— 动态规划逐轮松弛，O(VE)，可处理负权边和检测负环，是唯一能检测负环的单源最短路径算法
Floyd-Warshall —— 动态规划三层递推，O(V³)，一次性解决全源最短路径，代码极简但仅适用于小规模图
路径重构 —— 通过prev/nxt数组记录前驱/后继，从终点回溯到起点获取完整路径，三种算法均可扩展支持
算法选型 —— 根据图规模、是否有负权边、是否需要全源信息决定使用哪种算法
进阶扩展 —— DAG最短路径利用拓扑排序可达线性时间；双向搜索和A*针对单对查询大幅优化；Johnson算法融合Bellman-Ford与Dijkstra

十、练习题与思考

以下是几道经典的LeetCode题目，可以巩固对最短路径算法的理解：

LeetCode 743. 网络延迟时间 —— Dijkstra堆优化的典型应用，计算信号从源节点传播到所有节点所需的最短时间
LeetCode 787. K站中转内最便宜的航班 —— Bellman-Ford的变体，限制中转次数（即边数）的最短路径
LeetCode 1334. 阈值距离内邻居最少的城市 —— Floyd-Warshall全源最短路径的应用，统计每个城市在给定距离内可达的城市数量
LeetCode 1462. 课程表IV —— Floyd-Warshall传递闭包的应用，判断课程之间的前置依赖关系

思考题：如果图中同时存在正权边和负权边，但没有负权环，如何设计一种算法在大多数情况下比Bellman-Ford更快？提示：先对图进行分层处理，或使用Dijkstra结合势能函数——这正是Johnson算法的思路。