最短路径算法Dijkstra与Floyd

可视化演示

Dijkstra贪心逐步确定单源最短路径，Floyd动态规划更新全源距离矩阵，直观对比两种经典图算法的执行过程。

最短路问题

跑腿小哥小张的地图其实可以抽象成一张“带权图”：路口是图的顶点，道路是边，道路上的预计耗时就是边的权重。如果一个路口和另一个路口之间没有直接的路，我们就认为它们之间没有边；如果道路是单行道，就把它画成有方向的边。这样，任何一条送餐路线都对应图里的一条路径，路径的总耗时就是把沿途每条边的权重加起来。

最短路问题要回答的就是：在所有从起点 s 到终点 v 的路径中，哪一条的总权重最小？这个最小总权重记作 d(s,v)。

如果每条边的权重都正好是 1，那问题就退化成无权图最短路，直接用广度优先搜索 BFS 就能在 O(V+E) 时间内解决。但真实地图中每条路耗时不同，所以需要更通用的算法。先弄清楚是只求一个起点到所有点，还是要求任意两点之间，才能决定该请哪一位算法出场。

贪心策略：Dijkstra 的核心

小张的直觉很朴素：既然每条路耗时都不会是负数，那么已经被确认最短距离的那个路口，以后无论怎么绕路都不可能变得更短。所以他准备了一张距离表，起点写 0，其他路口暂时写“无穷大”；每次从还没确认的路口里挑距离最小的那个，把它从“待定”改成“确定”，然后沿着它的每条出路，看看能否让邻居的距离变得更小。这一步在算法里叫作“松弛”。

Dijkstra 的贪心之处，就是永远相信“当前距离最小的待定节点”已经拿到了最终答案。这个直觉只在边权非负时成立，因为任何绕路都会增加总耗时，不可能偷出更短的路径。

小张按这个规则一步步处理下去，等所有路口都变成“确定”状态时，距离表里就是仓库到全城每个路口的最短耗时。贪心策略虽然简单，但胜在每一步都建立在“边权非负”这个坚实前提上。

堆优化：让 Dijkstra 跑得更快

如果不做任何优化，小张每次都要在所有“待定”路口中扫描一遍找最小值，这就像把整个电话簿从头翻到尾只为找一个电话号码。当城市路口很多时，这种 O(V^2) 的做法会明显变慢。堆优化就是给小张配一个“叫号机”：所有待定路口按距离排成小顶堆，堆顶永远是最小值。

优先队列保存的是“候选距离 + 路口编号”。每松弛一条边，就把新的候选距离压进堆里；同一个路口可能被压入多次，所以取出堆顶后要先检查一下：如果取出的距离比距离表里当前记录的值大，说明这条记录已经过期，直接丢弃。这个技巧叫“惰性删除”。

经过堆优化后，Dijkstra 的时间复杂度从朴素版的 O(V^2+E) 变成 O((V+E)\log V)。在道路稀疏的大城市里，E 远小于 V^2，这种优化能让导航系统从“慢吞吞查电话簿”变成“秒响应叫号机”。

动态规划：Floyd 的全源速查表

公司看小张效率高，又给他派了个新任务：做一张全城速查表，让任意两个路口之间都能直接查到最短耗时。这时 Dijkstra 虽然也能做，但每次只能从一个起点出发；如果路口很多，反复跑 Dijkstra 也很贵。Floyd 算法的思路是用动态规划，把每个路口轮流当作“临时中转站”。

设 D_k[i][j] 表示“只允许经过前 k 个路口作为中转”时，i 到 j 的最短距离。考虑第 k 个路口时，从 i 到 j 要么完全不经过 k，要么经过 i→k→j。于是可以不断用中转点 k 来刷新整张表。

实现时用邻接矩阵初始化：i 到 i 的距离是 0，有直接边的点对填权重，没边就填无穷大。外层循环必须按 k 从小到大进行，让每个中转点只“上任”一次。等所有 k 都处理完，矩阵里就是任意两点之间的最短距离。Floyd 可以处理负权边，但不能有负权环；如果最后发现 dist[i][i] 变成负数，说明图里藏着一个“倒贴钱”的循环。

负权检测：Bellman-Ford 的补救

小张某天遇到一条奇怪的打折路段：经过它不扣时间，反而倒找时间。普通地图当然不会有这种路，但在金融套利、游戏数值等场景中，负权边是真实存在的。边权为负时，Dijkstra 的贪心结论会失效，因为一个路口可能先被确定距离，之后又从一条负权小路绕回来变得更短。

Bellman-Ford 算法不搞“每次选最近”的贪心，而是像夜班巡逻车一样，老老实实把每条边都扫一遍，连续扫 V-1 轮。为什么是 V-1 轮？因为一条不绕圈的简单路径最多包含 V-1 条边，信息沿着路径最多传播 V-1 次就能到达所有点。

如果完成 V-1 轮之后，再扫一遍所有边仍能让某个 d[v] 变小，那就说明存在负权环——因为在这个环里每绕一圈总耗时都会下降，最短路径根本不存在。Bellman-Ford 的时间复杂度是 O(VE)，虽然比 Dijkstra 慢，但它能接手 Dijkstra 不敢碰的负权场景。

复杂度对比：三个方案的性价比

现在小张手里有三套方案，选哪一套要看图的规模。Dijkstra 适合单源、非负、稀疏图；Floyd 适合全源、点数较少或边很密的图；Bellman-Ford 适合需要处理负权边或检测负环的场景。

空间上，Dijkstra 和 Bellman-Ford 只需要保存距离表 O(V)，Floyd 需要保存整个二维矩阵 O(V^2)。所以 Floyd 虽然能直接给出全源答案，但顶点数上千时内存也会很紧张。选算法不是选“最聪明的”，而是选“性价比最高的”。

应用选型：现实中怎么选

回到小张的公司：如果只是从仓库给顾客送餐，那就跑一趟 Dijkstra；如果想知道全国所有城市中转站两两之间的最低运输成本，那就用 Floyd；如果某些路线允许“补贴价”导致负权，那就必须让 Bellman-Ford 先检查负环。选择算法就像选交通工具：去楼下便利店走路就行，跨城要坐高铁，运重货得叫卡车。

导航系统里常用的 A* 算法就是在 Dijkstra 的基础上加了一个“朝着终点方向优先扩展”的启发式，让搜索更有方向感。而在物流系统中，如果城市数量不多但关系很密，Floyd 的一次矩阵计算能省下大量重复查询时间。选型的关键从来不是“背复杂度”，而是先回答：单源还是全源？有没有负权？图是稀疏还是稠密？

AI 应用场景

Python 演示

import heapq def dijkstra(graph, src):    n = len(graph)    dist = [float('inf')] * n    dist[src] = 0    pq = [(0, src)]    while pq:        d, u = heapq.heappop(pq)        if d > dist[u]:            continue        for v, w in graph[u]:            nd = d + w            if nd < dist[v]:                dist[v] = nd                heapq.heappush(pq, (nd, v))    return dist def floyd(graph):    n = len(graph)    INF = float('inf')    dist = [[INF] * n for _ in range(n)]    for i in range(n):        dist[i][i] = 0        for v, w in graph[i]:            dist[i][v] = w    for k in range(n):        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 if __name__ == "__main__":    graph = [        [(1, 2), (2, 5)],        [(2, 1), (3, 6)],        [(4, 3)],        [(4, 2), (5, 3)],        [(5, 1)],        []    ]    print("Dijkstra from 0:", dijkstra(graph, 0))    all_pairs = floyd(graph)    print("Floyd dist matrix:")    for row in all_pairs:        print(row)

1. dist = [float('inf')] * n初始化距离表，把所有顶点到起点的距离先设为无穷大。
2. pq = [(0, src)]优先队列从起点开始，起点距离为 0。
3. if d > dist[u]: continue这是惰性删除，跳过已经过期的堆记录。
4. nd = d + w计算经过 u 再到 v 的候选新距离。
5. for k in range(n):Floyd 外层循环，k 是当前允许使用的中转点。
6. if dist[i][k] + dist[k][j] < dist[i][j]:检查绕道 k 是否比 i 到 j 原来的路更短。

常见误区

面试题