最短路径（Dijkstra, Floyd）

🗺️ 高德地图怎么知道走哪条路最快？

你在高德地图上输入”从学校到火车站”，它瞬间给出三条路线——推荐路线、备选路线 1、备选路线 2。每条路线都标明了距离和预计时间。

它是怎么算出来的？

把城市地图抽象成一个有权图——交叉路口是顶点，道路是边，道路长度（或预计通行时间）是边的权重。“最短路径”问题就是：在这个加权图中，找出一条从起点到终点、边权和最小的路径。

最经典的两个最短路径算法：

• Dijkstra 算法——求”一个点到所有其他点”的最短路径（单源）
• Floyd-Warshall 算法——求”所有点到所有点”的最短路径（多源）

🧭 类比：坐飞机转机

你想从北京飞往三亚。没有直飞航班，你需要转机。

可能的转机方案：

• 北京 → 上海（2h）→ 三亚（3h）→ 总时间 5h
• 北京 → 广州（3h）→ 三亚（1.5h）→ 总时间 4.5h
• 北京 → 成都（2.5h）→ 三亚（3h）→ 总时间 5.5h

哪条路线总时间最短？这就是 Dijkstra 要解决的问题——在”所有可能的路径”中找到最短（最省时）的那一条。

---

🚀 Dijkstra——单源最短路径

适用条件

• 适用于有权图（边可以有权重）
• 权重必须非负（Dijkstra 无法处理负权边）
• 求从一个源点到所有其他顶点的最短路径

算法思想

Dijkstra 是贪心算法——每次从”未确定最短路径”的顶点中，选择距离源点最近的那个，然后用它更新其他顶点的距离。

通俗理解：从起点开始，不断"扩展"已知最短路径的区域。
每次已知区域向外扩展一步时，选那条最短的边。就像雨水在地上扩散——水总是先流向最近的低洼处。

过程演示

图（顶点 A~F，边上的数字是权重）：
    A ──6── B ──5── C
    |       |       |
    1       2       5
    |       |       |
    D ──1── E ──1── F

求从 A 到所有点的最短路径：

初始化：
dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞, dist[E]=∞, dist[F]=∞
已确定最短路径：{}

第 1 步：选距离最小的顶点 A (dist=0)
用 A 更新邻居：B(dist=6), D(dist=1)
已确定：{A}

第 2 步：选距离最小的顶点 D (dist=1)
用 D 更新 E(dist=1+1=2)
已确定：{A, D}

第 3 步：选距离最小的顶点 E (dist=2)
用 E 更新 B(dist=min(6, 2+2=4)=4), F(dist=2+1=3)
已确定：{A, D, E}

第 4 步：选距离最小的顶点 B (dist=4)
用 B 更新 C(dist=4+5=9)
已确定：{A, D, E, B}

第 5 步：选距离最小的顶点 F (dist=3)
用 F 更新 C(dist=min(9, 3+5=8)=8)
已确定：{A, D, E, F, B}

第 6 步：选距离最小的顶点 C (dist=8)
已确定：{A, D, E, F, B, C}

最终结果：
A→A=0, A→D=1, A→E=2, A→F=3, A→B=4, A→C=8

代码实现

import heapq

def dijkstra(graph, start):
    """
    graph: 邻接表 {v: [(neighbor, weight), ...]}
    start: 源点
    返回: {v: 最短距离}
    """
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    
    # 优先队列：(距离, 顶点)，距离最小的在堆顶
    pq = [(0, start)]
    
    while pq:
        d, v = heapq.heappop(pq)
        
        if d > dist[v]:
            continue  # 已经处理过了（d 不是最新值）
        
        for neighbor, weight in graph[v]:
            nd = d + weight
            if nd < dist[neighbor]:
                dist[neighbor] = nd
                heapq.heappush(pq, (nd, neighbor))
    
    return dist

复杂度分析

实现方式	时间复杂度	说明
简单数组	O(V²)	每次找最小 distance 遍历所有顶点
优先队列	O((V+E) log V)	用堆实现，最常用

💡 为什么 Dijkstra 不能处理负权边？ Dijkstra 的核心是”从已确定最短路径的点扩展”——一旦一个点的最短路径被确定，就不会再被更新。但如果有负权边，后面可能出现一条”更短的路”指向已经确定了的点。要处理负权边，需要用 Bellman-Ford 算法。

---

🔄 Floyd-Warshall——所有点对最短路径

算法思想

Floyd 算法用动态规划的思路：逐步允许经过更多的”中间点”，不断更新任意两点之间的最短距离。

# 核心思想：
# dp[k][i][j] = 从 i 到 j，允许经过前 k 个顶点时的最短距离
# dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
# 空间优化后可以压缩成二维数组

🚏 类比：逐步开放的中转站

假设全国城市之间，一开始你只能直飞（不允许中转）。Floyd 的每一步”开放一个新城市作为中转站”：

第 1 步：只允许在北京中转 → 更新所有”经过北京”比原来更短的路线 第 2 步：允许在北京和上海中转 → 继续更新 第 3 步：允许在北京、上海和广州中转 → ……

当所有城市都开放作为中转站后，你就得到了任意两个城市之间的最短路线。

代码实现

def floyd_warshall(graph):
    """
    graph: 邻接矩阵，graph[i][j] = 从 i 到 j 的权重（∞ 表示无直接边）
    返回: (dist矩阵, next矩阵) 可重构最短路径
    """
    n = len(graph)
    dist = [row[:] for row in graph]  # 复制距离矩阵
    
    for k in range(n):  # 允许经过顶点 k
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

复杂度

• 时间复杂度：O(V³) —— 三层嵌套循环
• 空间复杂度：O(V²) —— 二维距离矩阵

和 Dijkstra 的对比

维度	Dijkstra	Floyd
解决的问题	单源 → 所有点	所有点 → 所有点
时间复杂度	O((V+E)log V)	O(V³)
适用图	非负权图	任意（可处理负权，但不能有负权环）
实现复杂度	中等	简单（就三层循环）
V 较大时	✅ 可行（稀疏图）	❌ 不适用（V 超 1000 就慢）

---

🎯 实际应用

# 场景 1：导航系统（Dijkstra）
# 中国城市公路网 ≈ 300 个城市，边 ≈ 5000 条
# Dijkstra + 优先队列：O((300+5000) log 300) ≈ 毫秒级

# 场景 2：社交网络的"一度、二度人脉"
# BFS（无权图最短路径）就够了

# 场景 3：交通网络分析（Floyd）
# 分析一个城市的 50 个地铁站之间的最短路径
# Floyd：O(50³) = 125k → 毫秒级，可行且代码简单

# 场景 4：随时查询任意两个城市的最短距离
# 先用 Floyd 预处理出所有点对最短路径（O(V³)）
# 每次查询时直接取 dist[u][v] → O(1)

---

📝 小结

概念	一句话
Dijkstra	贪心 + 优先队列——每次选最近的点扩展
适用场景	非负权图，单源最短路径
Floyd	动态规划——三层循环，逐步允许更多中间点
适用场景	小图的所有点对最短路径（V < 1000）
负权边	Dijkstra 不能处理，Floyd 可以但不能有负权环

🎯 思考题：如果一个图的边权都是 1（无权图），Dijkstra 会退化成什么算法？还能用 Dijkstra 吗？（提示：回想 BFS）

为什么先学这个？ 最短路径是最重要的图算法之一。另一个重要的图算法是最小生成树（Kruskal, Prim）——它找的不是”两点之间”最短，而是”连接所有点”的最省方案。