4. Dijkstra算法：从原理到实战

Dijkstra算法，说白了就是「找最短路径」的祖师爷。我当年刚入行时，第一个接触的路径规划算法就是它。你想想看，地图上两个点之间，哪条路最短？Dijkstra给出了一个非常优雅的答案。

4.1 算法核心思想

Dijkstra算法的本质，是一个「贪心+动态规划」的组合。它从起点开始，一层层向外扩散，每次选择当前已知最短的路径继续探索。嗯，这里要注意：它要求所有边的权重不能为负数。

我个人习惯把它的工作方式想象成「水波扩散」——你往平静的水面扔一颗石子，波纹会一圈圈向外扩散，最先到达岸边的那一圈波纹，就是最短路径。

核心三要素：

距离数组：记录从起点到每个节点的当前最短距离
访问标记：标记哪些节点已经找到了最短路径
优先队列：每次取出距离最小的未访问节点

4.2 优先队列实现

为什么用优先队列？我刚开始学的时候也纳闷——用普通数组不行吗？行是行，但效率差太多了。普通数组每次找最小值要O(n)，优先队列只要O(log n)。

我在项目中遇到过一个问题：地图上有几千个节点，用普通数组实现Dijkstra，跑一次要好几秒。换成优先队列后，瞬间降到几十毫秒。这就是数据结构的威力。

下面是我常用的C++实现模板：

#include <vector>
#include <queue>
#include <limits>

using namespace std;

// 图的邻接表表示
vector<vector<pair<int, int>>> graph;  // (邻居节点, 边权重)

vector<int> dijkstra(int start, int n) {
    // 距离数组，初始化为无穷大
    vector<int> dist(n, numeric_limits<int>::max());
    dist[start] = 0;
    
    // 优先队列：存储 (距离, 节点编号)
    // 默认是大顶堆，用greater变成小顶堆
    priority_queue<pair<int, int>, 
                   vector<pair<int, int>>, 
                   greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        // 如果当前距离大于已知最短距离，跳过
        if (d > dist[u]) continue;
        
        // 遍历邻居
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            
            // 松弛操作
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

避坑指南：我曾经在优先队列里忘记用greater，结果跑出来全是错误路径。默认的priority_queue是大顶堆，取出来的是最大距离，那算法就完全乱套了。记住：Dijkstra要用小顶堆！

4.3 最优性证明

为什么Dijkstra算法一定能找到最短路径？这个问题我面试时被问过好几次。其实证明思路很直观：

归纳法证明：

基础情况：起点到自身的距离为0，显然是最短的
归纳步骤：假设已经找到了k个节点的最短路径，那么第k+1个被选中的节点，它的距离一定是全局最短的

为什么会这样？因为所有边权非负，任何绕路的路径只会让距离变大。你想想看，如果有一条更短的路径能到当前节点，那它早就被优先队列弹出来了。

重要前提：边权必须非负！如果有负权边，Dijkstra会失效。我在一个项目中遇到过这种情况——地图上有「下坡路」导致负权值，结果Dijkstra跑出来的路径完全不对。后来换成了Bellman-Ford算法才解决。

4.4 栅格地图上的仿真

在实际的机器人项目中，我们经常把环境抽象成栅格地图。每个格子要么是空地（可通行），要么是障碍物（不可通行）。

下面是我在仿真中常用的8邻域搜索方式：

// 栅格地图上的Dijkstra
// 0表示空地，1表示障碍物
vector<vector<int>> grid;  // 地图数据
int rows, cols;             // 地图尺寸

// 8个方向的移动代价
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int cost[] = {14, 10, 14, 10, 10, 14, 10, 14};  // 对角移动代价为14，直线为10

vector<vector<int>> dijkstraGrid(int startX, int startY) {
    // 距离矩阵
    vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
    dist[startX][startY] = 0;
    
    // 优先队列
    priority_queue<tuple<int, int, int>, 
                   vector<tuple<int, int, int>>, 
                   greater<tuple<int, int, int>>> pq;
    pq.push({0, startX, startY});
    
    while (!pq.empty()) {
        auto [d, x, y] = pq.top();
        pq.pop();
        
        if (d > dist[x][y]) continue;
        
        // 搜索8个方向
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 边界检查
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
            // 障碍物检查
            if (grid[nx][ny] == 1) continue;
            
            int newDist = d + cost[i];
            if (newDist < dist[nx][ny]) {
                dist[nx][ny] = newDist;
                pq.push({newDist, nx, ny});
            }
        }
    }
    
    return dist;
}

仿真结果解读：

距离矩阵中每个格子的值，代表从起点到该格子的最短路径长度
障碍物格子的距离保持为无穷大
通过回溯距离矩阵，可以重建完整的路径

我在做AGV（自动导引车）项目时，就是用这个算法做全局路径规划。不过要注意，栅格地图的分辨率很关键——格子太大，路径不够精细；格子太小，计算量暴增。我一般取机器人直径的1/3作为格子大小，效果还不错。

4.5 算法复杂度分析

实现方式	时间复杂度	空间复杂度	适用场景
普通数组	O(V²)	O(V)	稠密图，节点少
二叉堆优先队列	O((V+E)logV)	O(V+E)	稀疏图，通用场景
斐波那契堆	O(VlogV+E)	O(V+E)	大规模图，理论最优

我的建议：实际工程中，二叉堆实现就够用了。斐波那契堆虽然理论更快，但常数大，实现复杂，性价比不高。我曾经在项目中试过斐波那契堆，结果因为实现bug调试了两天，最后还是换回了二叉堆。

4.6 知识体系总览

下面这张图总结了Dijkstra算法的核心知识结构：

Dijkstra算法虽然经典，但也有局限性。比如它不知道目标点在哪，会盲目地朝所有方向扩散。下一章我们要讲的A*算法，就是在这个基础上加了启发式信息，让搜索更有方向感。

可可精品资料库

📚 课程目录

4. Dijkstra算法：从原理到实战

4.1 算法核心思想

4.2 优先队列实现

4.3 最优性证明

4.4 栅格地图上的仿真

4.5 算法复杂度分析

4.6 知识体系总览