第208篇 Dijkstra算法——最短路径的经典解法

郑伟强dev

316人浏览 · 2026-08-19 04:26:16

郑伟强dev · 2026-08-19 04:26:16 发布

上一篇讲了图搜索的基础框架——离散化、图的构建、搜索的基本流程。今天讲最经典的图搜索算法：Dijkstra。

Dijkstra算法是1956年荷兰计算机科学家Edsger Dijkstra提出的。距今快70年了，但依然是很多规划算法的基础，也是面试必考内容。面试时被问到"说说你了解的图搜索算法"，Dijkstra是必答项。

一、算法思想

Dijkstra的目标很明确：在带权图中，找到从起点到所有其他节点的最短路径。注意是"所有其他节点"，不只是某一个终点。

核心思想是"贪心扩展"——每次从"待处理"集合中，选出离起点最近的那个节点，然后用它去更新邻居的距离。这个过程不断重复，直到所有节点都被处理过。

打个比方：你站在一个城市的中心，想知道去所有地方怎么走最快。Dijkstra的做法是：先看1km内能到哪，再看2km内能到哪，3km、4km……像水波纹一样一圈一圈往外扩散。每扩散一圈，就记录下到每个地方的最短距离。

这个"水波纹"的比喻很关键——Dijkstra的搜索范围是一个以起点为圆心的圆，随着距离增大而不断扩大。

二、算法流程

import heapq

def dijkstra(graph, start):
    # dist[node] = 从start到node的最短距离
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    
    # 优先队列：(距离, 节点)
    pq = [(0, start)]
    visited = set()
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    return dist

代码的核心就三步：

从优先队列取出距离最小的节点
遍历它的所有邻居
如果经过当前节点到邻居的距离更短，就更新

来看一个具体例子。假设有一个5节点的图：

A --1-- B --2-- C | | | 4 3 1 | | | D --2-- E --3-- F

从A出发，Dijkstra的执行过程：

初始化：dist[A]=0，其他=inf
处理A：更新B=1, D=4
处理B（距离最小=1）：更新C=3, E=4
处理C（距离=3）：更新F=4
处理D或E（距离=4）：...

最终得到从A到所有节点的最短距离。

三、为什么Dijkstra能找到最短路径？

关键性质：当Dijkstra把一个节点标记为"已访问"时，它到起点的距离一定是最短的。

为什么？因为Dijkstra总是选距离最小的节点来扩展。如果存在一条更短的路径，那条路径上的某个中间节点一定还没被访问（否则早就更新了），而那个中间节点的距离一定比当前节点小——矛盾。

这个证明依赖一个前提：边的权重非负。如果有负权边，Dijkstra就不对了。不过机器人规划中边的权重代表距离或代价，不可能为负，所以不用担心。

四、Dijkstra在机器人规划中的应用

在机器人规划中，Dijkstra的典型用法：

# 2D网格地图上的Dijkstra
def dijkstra_grid(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[start[0]][start[1]] = 0
    pq = [(0, start)]
    came_from = {}
    
    while pq:
        d, (r, c) = heapq.heappop(pq)
        
        if (r, c) == goal:
            return reconstruct_path(came_from, goal)
        
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0:  # 不是障碍物
                    cost = d + 1
                    if cost < dist[nr][nc]:
                        dist[nr][nc] = cost
                        came_from[(nr, nc)] = (r, c)
                        heapq.heappush(pq, (cost, (nr, nc)))
    return None

工程上，Dijkstra常用于：

计算"距离场"——每个格子到最近障碍物的距离。距离场在路径规划中很有用——规划器可以优先选择距离场值大的区域（离障碍物远），提高安全性。
全局路径规划（地图已知，求最短路径）
作为A算法的基础（A就是加了启发式的Dijkstra）

五、Dijkstra的局限性

Dijkstra能保证找到最短路径，但有一个明显的问题：它不知道终点在哪。

Dijkstra像水波纹一样均匀扩散，不管终点在什么方向，它都要把所有距离更近的节点都探索一遍。如果地图很大，终点很远，Dijkstra会探索大量无关的节点。

举个例子：100x100的网格，起点在左下角，终点在右上角。Dijkstra会探索大约半个网格（5000个节点），而实际上最短路径只需要走约140步。浪费了90%以上的计算量。

另一个问题是内存占用。Dijkstra需要存储所有节点的距离值。对于大规模地图（比如自动驾驶的高精地图，节点数可能上亿），内存消耗是个实际问题。

这就是为什么需要A*——A*用启发式函数告诉搜索"终点在哪个方向"，避免盲目扩散。后面会详细讲。

六、面试实战

Q：Dijkstra和BFS有什么区别？ A：BFS是Dijkstra在等权图上的特例。BFS用普通队列（FIFO），Dijkstra用优先队列。等权图中所有边权重相同，优先队列退化成普通队列。换句话说，BFS就是"无权图版"的Dijkstra。

Q：Dijkstra的时间复杂度是多少？ A：用二叉堆（优先队列）实现：O((V+E)logV)。用斐波那契堆可以优化到O(VlogV + E)，但工程上很少用——斐波那契堆的常数因子太大，实际反而更慢。对于稀疏图（E≈V），二叉堆版本已经够好了。

Q：Dijkstra能处理负权边吗？ A：不能。负权边会导致"已访问"节点的距离被更新，破坏Dijkstra的贪心策略。比如A→B权重3，A→C权重5，C→B权重-4。Dijkstra先处理B（距离3），但后来发现A→C→B距离只有1。负权边用Bellman-Ford算法，时间复杂度O(VE)。

Q：Dijkstra和A*的关系是什么？ A：A* = Dijkstra + 启发式函数。当h(n)=0时，A退化为Dijkstra。当h(n)等于真实代价时，A只走最短路径（但现实中不可能知道真实代价）。工程上，Dijkstra适合"一对多"的最短路径（比如计算距离场），A*适合"一对一"的路径规划。

Q：实际项目中你用过Dijkstra吗？ A：用过。之前做仓储AGV时，全局地图用Dijkstra计算距离场——每个格子到最近货架的距离。然后A*规划路径时，把距离场作为额外的代价项，让路径尽量远离货架。距离场只需要算一次（地图不变时），后续每次规划都能用。