从算法到人工智能 · 第 16 课：最短路径与贪心——每次挑眼前最好的

导航软件怎么算出从你家到机场的最快路线？地图上成千上万条路，它不可能每条都试一遍。答案藏在两个算法里：Dijkstra 算法（算最短路径）和它背后的思想——贪心（greedy）。

这一课，我们认识"贪心"这种最直白的算法策略，并用它推导出 Dijkstra 最短路径算法——这是导航、网络路由、游戏 AI 寻路的底层机制。

一、贪心是什么：每一步都挑眼前最好的

贪心策略：在每一步，都做出当前看起来最优的选择，不去考虑长远的后果。走一步看一步，希望"局部最优"堆起来就是"全局最优"。

经典例子——找零钱。用最少的硬币凑出目标金额，贪心做法是：每次拿面额最大的硬币。

def greedy_change(amount, coins):
    coins.sort(reverse=True)   # 从大到小
    result = []
    for c in coins:
        while amount >= c:
            result.append(c)
            amount -= c
    return result

print(greedy_change(63, [25, 10, 5, 1]))   # [25,25,10,1,1,1] 6 枚

在这个例子里，贪心是对的。但贪心不一定总是对——看这个坑：

# 硬币面额 [5, 4, 1]，凑 8
print(greedy_change(8, [5, 4, 1]))   # [5,1,1,1] → 4 枚（贪心）
# 但最优是 [4,4] → 2 枚！贪心失败了

贪心的核心问题：什么时候"眼前最好"能保证"全局最好"？ 这需要证明，不是所有问题都能用贪心。但一旦能用，贪心往往是最快的解法。

二、贪心的经典应用

1. 区间调度（安排最多不冲突的活动）

经典问题：有一堆活动，每个有开始和结束时间，问最多能安排几个互不冲突的。贪心策略：每次选"结束最早"的活动。

def max_activities(activities):
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    count = 0
    last_end = float("-inf")
    for start, end in activities:
        if start >= last_end:   # 不冲突
            count += 1
            last_end = end
    return count

# (开始, 结束)
acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(max_activities(acts))   # 4

为什么"选结束最早的"对？ 直觉：结束越早，剩下的时间越多，能塞进的活动就可能越多。选结束最早，永远是"最不贪心占用未来"的选择。

2. 哈夫曼编码（贪心 + 堆）

压缩文件时，让出现频率高的字符用短编码、频率低的用长编码，能省空间。哈夫曼算法用贪心 + 小顶堆，每次合并两个频率最低的：

import heapq
from collections import Counter

def huffman_length(text):
    freq = Counter(text)   # 统计频率
    heap = list(freq.values())
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = a + b
        total += merged
        heapq.heappush(heap, merged)
    return total

text = "this is an example for huffman encoding"
print(huffman_length(text))

体会：贪心策略"每次合并最小的两个"，配上堆（第 13 课）高效取最小，是贪心和数据结构的完美配合。

三、Dijkstra：贪心求最短路径

现在回到导航问题。一张带权图（边上有距离），求从起点到所有点的最短路径。这就是 Dijkstra 算法。

贪心思想：每次都从"还没确定最短距离的点"里，选当前距离最小的那个点，确定它的最短距离，然后用它去"松弛"（更新）邻居的距离。

import heapq

def dijkstra(graph, start):
    dist = {node: float("inf") for node in graph}   # 到各点的距离，初始无穷
    dist[start] = 0
    heap = [(0, start)]   # (距离, 节点)，小顶堆
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:       # 过期的旧距离，跳过
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:   # 找到更近的路 → 松弛
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist

# 邻接表：{节点: [(邻居, 距离)]}
graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 1), ("D", 5)],
    "C": [("D", 8), ("E", 10)],
    "D": [("E", 2)],
    "E": [],
}
print(dijkstra(graph, "A"))
# A→B=4, A→C=2, A→D=7(A→C→D? 其实A→B→D=9, A→C→D=10)...

一步步看 Dijkstra 怎么贪心（从 A 出发）：

1. 起点 A 距离 0，其他 ∞。选 A（距离最小）。
2. 用 A 松弛邻居：B=4，C=2。
3. 未确定的点里，C（距离 2）最小 → 选 C，松弛邻居：D=2+8=10，E=2+10=12。
4. 未确定的点里，B（距离 4）最小 → 选 B，松弛：C=4+1=5（比 2 大，不更新），D=4+5=9（比 10 小，更新为 9）。
5. 未确定的点里，D（距离 9）最小 → 选 D，松弛：E=9+2=11（比 12 小，更新）。
6. 最后 E（距离 11）确定。

最终：A→B=4，A→C=2，A→D=9，A→E=11。

为什么要用堆？

第 3 步"从未确定点里选距离最小的"——如果每次线性扫描，是 O(n²)。用小顶堆，O(log n) 就能取出最小。所以 Dijkstra 配堆，复杂度 O((V+E) log V)。这就是第 13 课堆的又一个主场。

四、贪心 vs 动态规划（提前打个照面）

贪心和后面要学的动态规划（DP），是两种相反的策略：

怎么区分：贪心是"赌眼前这一步对了就对了"；DP 是"把每一步的所有可能都算一遍，保证不错过最优"。贪心错了就错（如 5/4/1 凑 8），DP 永远对但更费劲。

五、最短路径的扩展：Bellman-Ford 与 Floyd

Dijkstra 很强，但它有两个"不能"：不能处理负权边（贪心假设已失效），一次只能求一个起点到所有点的最短路。有两个补充算法补上这些缺口。

1. Bellman-Ford：能扛负权边

思路是"松弛（relax）"：反复遍历所有边，如果发现走这条边能缩短距离，就更新。最多松弛 n-1 轮（n 是节点数）。

INF = float('inf')
edges = [(0, 1, 4), (1, 2, -3), (0, 2, 5)]   # (起点, 终点, 权重)，有负权 -3
n = 3
dist = [INF] * n
dist[0] = 0
for _ in range(n - 1):            # 最多 n-1 轮
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
print(dist[2])   # 1（0→1→2：4-3=1，比直接 0→2 的 5 更短）

复杂度 O(n·m)，m 是边数。它还能检测负环：如果第 n 轮还能松弛，说明存在负权环（越走越短，没有最短路）。

2. Floyd：一次求"所有点对"的最短路

如果想一次算出"任意两点间的最短路"（比如交通网络），用 Floyd，核心是一个三重循环的动态规划：

n = 4
G = [[0, 4, INF, INF],
     [INF, 0, 1, 2],
     [INF, INF, 0, INF],
     [INF, INF, INF, 0]]
D = [row[:] for row in G]
for k in range(n):                 # 允许经过中间点 k
    for i in range(n):
        for j in range(n):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
print(D[0][3])   # 6（0→1→3 = 4+2）

复杂度 O(n³)，节点不多时非常好用，代码也短。

三个最短路径算法怎么选

六、最小生成树：用最少的线连起所有点

又一个图里的经典问题：

有 n 个城市，两两之间修路有不同成本。怎么修，才能让所有城市连通，且总成本最低？

答案是一棵最小生成树（MST，Minimum Spanning Tree）——连通所有节点、无环、边权和最小。两个经典算法，都是贪心（正好承接本课主题）。

1. Kruskal：从最短的边开始挑

思路：把所有边按权值从小到大排序，依次尝试加入；如果这条边不会成环（两端还没连通）就收下。判断"会不会成环"正好用第 14 课的并查集。

class UF:
    def __init__(self, n): self.p = list(range(n))
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb: self.p[ra] = rb

edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,4)]
edges.sort(key=lambda e: e[2])     # 按权值排序
uf = UF(4); mst = []
for u, v, w in edges:
    if uf.find(u) != uf.find(v):   # 不成环才收
        uf.union(u, v)
        mst.append((u, v, w))
print(mst, "总权:", sum(w for _,_,w in mst))
# [(1,2,1),(1,3,2),(0,2,3)] 总权 6

2. Prim：从当前连通块往外"长"

思路：从一个点出发，每次挑一条连到当前连通块、权值最小的边，把新点拉进来。用最小堆维护候选边。

import heapq
g = {0:[(1,4),(2,3)], 1:[(0,4),(2,1),(3,2)], 2:[(0,3),(1,1),(3,4)], 3:[(1,2),(2,4)]}
vis = {0}
pq = [(w, 0, v) for v, w in g[0]]; heapq.heapify(pq)
mst2 = []
while pq and len(vis) < 4:
    w, u, v = heapq.heappop(pq)
    if v in vis: continue
    vis.add(v); mst2.append((u, v, w))
    for nv, nw in g[v]:
        if nv not in vis: heapq.heappush(pq, (nw, v, nv))
print(mst2, "总权:", sum(w for _,_,w in mst2))   # 总权 6

两种算法殊途同归：Kruskal 适合稀疏图，Prim 适合稠密图，都是 O(m log n) 级别。

七、A*：带着"方向感"的搜索

BFS 找最短路是"一圈一圈无脑往外扩"，没有方向感。A* 给它加了个"启发函数"——优先探索"看起来离目标更近"的节点。

在网格寻路里，常用曼哈顿距离当启发：

import heapq
INF = float('inf')
start, goal = (0, 0), (4, 4)
def h(p): return abs(p[0]-goal[0]) + abs(p[1]-goal[1])   # 启发：曼哈顿距离
open_set = [(h(start), 0, start)]
g_score = {start: 0}
cur = start
while open_set:
    _, g, cur = heapq.heappop(open_set)
    if cur == goal: break
    for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        nx, ny = cur[0]+dx, cur[1]+dy
        if 0 <= nx < 5 and 0 <= ny < 5:
            ng = g + 1; nb = (nx, ny)
            if ng < g_score.get(nb, INF):
                g_score[nb] = ng
                heapq.heappush(open_set, (ng + h(nb), ng, nb))
print("到达目标:", cur == goal)   # True

关键：优先级用 g + h——g 是已走距离，h 是"预估还剩多远"。只要 h 不高估（曼哈顿距离就满足），A* 一定能找到最短路，而且通常比 BFS 少探索很多节点。它广泛用于游戏寻路、地图导航。

八、复杂度小结

九、动手时间 🎯

实验 1：贪心 vs 最优（看贪心怎么"翻车"）

def greedy_change(amount, coins):
    coins.sort(reverse=True)
    result = []
    for c in coins:
        while amount >= c:
            result.append(c)
            amount -= c
    return result

# 贪心翻车：凑 8，面额 [5,4,1]
print("贪心:", greedy_change(8, [5, 4, 1]))   # [5,1,1,1] 4枚
print("最优: [4,4] 只需 2 枚")

体会：这个例子说明贪心不是万能的。为什么 25/10/5/1 能贪心、5/4/1 不能？因为前者有"整除"性质，后者没有。这提醒我们：用贪心前，先想清楚它是不是真的最优。

实验 2：区间调度，亲手验证"选最早结束"

def max_activities(activities):
    activities.sort(key=lambda x: x[1])
    count, last_end = 0, float("-inf")
    picked = []
    for start, end in activities:
        if start >= last_end:
            picked.append((start, end))
            count += 1
            last_end = end
    return count, picked

acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(max_activities(acts))

实验 3：Dijkstra 求最短路径（跑上面的图）

import heapq

def dijkstra(graph, start):
    dist = {n: float("inf") for n in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for nb, w in graph[node]:
            nd = d + w
            if nd < dist[nb]:
                dist[nb] = nd
                heapq.heappush(heap, (nd, nb))
    return dist

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 1), ("D", 5)],
    "C": [("D", 8), ("E", 10)],
    "D": [("E", 2)],
    "E": [],
}
print(dijkstra(graph, "A"))
# 对照手工：A→B=4, A→C=2, A→D=9, A→E=11

实验 4（挑战）：Dijkstra 带"记录路径"

在求最短距离的同时，记录从起点到每个点的最短路径：

import heapq

def dijkstra_path(graph, start, target):
    dist = {n: float("inf") for n in graph}
    dist[start] = 0
    prev = {start: None}        # 记录"从哪来"
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        if node == target:      # 到目标了，重建路径
            path = []
            while node is not None:
                path.append(node)
                node = prev[node]
            return path[::-1], d
        for nb, w in graph[node]:
            nd = d + w
            if nd < dist[nb]:
                dist[nb] = nd
                prev[nb] = node
                heapq.heappush(heap, (nd, nb))
    return None, float("inf")

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 1), ("D", 5)],
    "C": [("D", 8), ("E", 10)],
    "D": [("E", 2)],
    "E": [],
}
path, d = dijkstra_path(graph, "A", "E")
print("路径:", path, "距离:", d)   # 路径: A→B→D→E，距离 11

体会：prev 数组是"最短路"类算法的通用技巧——每个节点记下"我从哪来"，最后从目标倒着走回起点。导航软件就是这么给你画出路线的。

十、小结

1. 贪心 = 每一步挑眼前最好，局部最优不一定全局最优（5/4/1 凑 8 会翻车），用前要想清楚。
2. Dijkstra = 贪心 + 堆：每次选距离最小的点确定，再松弛邻居，复杂度 O((V+E) log V)——导航、路由的底层。
3. 贪心赌"眼前对就全对"，DP 算"所有可能不错过"——后面的主角 DP，就是那个"更稳但更费劲"的策略。

先别急着往后翻，把 Dijkstra 亲手跑一遍，再感受下"贪心翻车"的例子——这两样都体会到了，你对"算法策略"的理解就上了一个台阶。