CC++ & Algorithm

单源最短路——Dijkstra算法

困难5
语言版本：C++
概述：Dijkstra算法就像是一个“寻路小侦探”，帮我们从起点出发，一步步找到到其他所有点的最短路径，但只能用在路都是正数的情况下。

Dijkstra算法：正数路上的最短路径侦探

同学们，想象你是快递员，要从公司出发，把快递送到城市的各个小区。城市里有很多路口（顶点），路口之间有不同的道路（边），每条路都有正的长度（正权值）。你想知道从公司到每个小区的最短距离是多少。这时候，我们可以请出“小侦探”Dijkstra，它专门帮我们在所有道路都是正数的情况下，快速找出从起点到所有其他点的最短路径。

Dijkstra的工作方式很像一个聪明的寻路策略：它每次都从当前所有“未确定”的路口里，挑一个距离起点最近的路口，然后从这里出发，看看能不能让其他路口的距离变得更短。就像你玩游戏时，先走最近的一步，再一步步扩大探索范围。因为所有道路都是正数，已经确定的最短距离绝对不会再被后面更远的路径变短，所以Dijkstra可以放心地“拍板定案”。

下面我们详细拆解它的每一步。

什么是Dijkstra算法？

Dijkstra算法是一种单源最短路算法，它能求出一个起点到图中其他所有顶点的最短路径长度。它假设所有边的权值都是非负数（即≥0，实际上正数就可以了，0也行）。如果图里有负数路，它就会“上当”，所以记住：Dijkstra只适用于非负权图。

想象你在操场上玩“寻宝游戏”，每个宝藏点之间有小路，每条小路都有步数（正数）。你想知道从起点出发，到每个宝藏点最少要走多少步。Dijkstra就帮你一步步模拟这个过程。

算法的核心思想

Dijkstra的核心是贪心思想：每次从未确定最短距离的顶点中，选一个当前距离最小的顶点，把它“确定”下来（标记为已探索），然后尝试用它更新其他相邻顶点的距离。

这个贪心能行得通，是因为所有边权为正，所以一旦某个顶点的距离被确定（即它成为当前最小未被选的），后面任何路径都不可能再让这个距离变小——因为任何后续路径都要先绕到其他更远的顶点，再加上正数边，只会更大。

算法步骤详解

我们用生活例子来理解：假设公司是0号路口，有5个路口（0~4），道路图如下（数字是长度）：

0--6--1
|     |
1     5
|     |
3--2--2

（实际图是之前代码里的邻接矩阵，这里示意）

步骤1：初始化

  • 准备一个数组 dist，记录从起点到每个路口当前已知的最短距离。起点自己为0，其他都设为无穷大（用一个大数表示）。
  • 准备一个布尔数组 visited，标记每个路口是否已确定最短距离（即是否已探索），初始全部未探索。

步骤2：循环N-1次（N是顶点数）

  • 在未探索的顶点中，找出 dist 值最小的那个顶点 u。
  • 把它标记为已探索（表示它的最短距离已经确定）。
  • 遍历所有与 u 直接相连的顶点 v（即 graph[u][v] 不为0），并且 v 尚未探索：
    • 如果 dist[u] + graph[u][v] < dist[v]，就更新 dist[v] 为这个更小的值（这叫“松弛操作”）。

步骤3：输出结果
最后 dist 数组里就是起点到每个顶点的最短距离。如果某个顶点始终是无穷大，说明它不可达。

生活类比：
你像侦探一样，手里拿着一个“当前最短距离”名单。第一步，你站在公司（0号），看到相邻路口有1号（6步）和3号（1步）。你把3号记作当前最短（1步），然后决定先去3号。到了3号，发现从这里可以到1号（2步）和4号（1步），于是更新1号的距离为1+2=3步（比原来的6步短），4号距离为1+1=2步。然后你在未探索的（1号、2号、4号）中再挑最小的——此时4号是2步，于是去4号……如此重复，直到所有路口都去过。

代码实现（基础版）

下面是用邻接矩阵和普通循环实现的Dijkstra。这个版本适合顶点数不多（比如几百以内）的情况。代码变量都用了简短英文单词，每一行都有中文注释，方便你理解。

#include <iostream>
#include <climits>   // 用于INT_MAX
using namespace std;

int main() {
    const int N = 5;   // 路口数量
    // 邻接矩阵，0表示没有直接道路，正数表示道路长度
    int graph[N][N] = {
        {0, 6, 0, 1, 0},
        {6, 0, 5, 2, 2},
        {0, 5, 0, 0, 5},
        {1, 2, 0, 0, 1},
        {0, 2, 5, 1, 0}
    };

    int dist[N];          // 从0号路口到每个路口的最短距离
    bool visited[N] = {false};  // 是否已确定最短距离（已探索）

    // 1. 初始化：除了起点，其他都设为无穷大
    for (int i = 0; i < N; ++i) {
        dist[i] = INT_MAX;
    }
    dist[0] = 0;           // 起点到自己的距离是0

    // 2. 主循环：每次确定一个顶点的最短距离，共N-1次（因为起点已确定）
    for (int count = 0; count < N - 1; ++count) {
        // 找出未探索顶点中 dist 最小的那个
        int u = -1;             // 当前找到的最小距离的顶点编号，-1表示没找到
        int minDist = INT_MAX;  // 当前找到的最小距离
        for (int i = 0; i < N; ++i) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                u = i;
            }
        }
        // 如果所有顶点都已探索或剩下的距离都是无穷大，提前结束
        if (u == -1) break;

        visited[u] = true;      // 把u标记为已确定

        // 从u出发，更新所有相邻且未探索的顶点v的距离
        for (int v = 0; v < N; ++v) {
            if (graph[u][v] != 0 && !visited[v]) {
                int newDist = dist[u] + graph[u][v];
                if (newDist < dist[v]) {
                    dist[v] = newDist;   // 松弛成功，更新
                }
            }
        }
    }

    // 3. 输出结果
    cout << "从0号路口到各路口的最短距离:\n";
    for (int i = 0; i < N; ++i) {
        if (dist[i] == INT_MAX) {
            cout << "到" << i << "号路口: 不可达\n";
        } else {
            cout << "到" << i << "号路口: " << dist[i] << "\n";
        }
    }
    return 0;
}

运行结果：

从0号路口到各路口的最短距离:
到0号路口: 0
到1号路口: 3
到2号路口: 7
到3号路口: 1
到4号路口: 2

你可以自己验证：0→3（1步），3→4（1步）→1（2步）→2（5步），确实是最短。

为什么不能处理负权边？

Dijkstra的“小侦探”有个洁癖：它认为已经选出来的最短距离，以后不会再变短了。这个假设只在所有边权都为非负数时成立。如果存在负权边，可能出现这种情况：某个顶点被选为“已确定”后，后面发现有一条更长的路径，但因为中间有一条很短的负权边，反而让总距离变得更短！那Dijkstra就发现不了，因为它已经“定案”了。

比如你从0到1有两条路：0→1（长度5），0→2→1（长度4 + (-2) = 2）。如果先用Dijkstra，看到0→1是5，0→2是4，它会先选0→2作为当前最小，更新到1的距离为4-2=2（比5小）。但注意，它把2标记为已确定后，发现1的更新后距离不是最小的（因为还有0→1的5），所以下一个选的其实是1？算法流程其实会正确处理？——但如果有更复杂的图，比如0→1 (6), 0→2 (5), 2→1 (-3), 1→2 (1)，Dijkstra可能先选最小距离的2（5），然后更新1为5-3=2，然后1被标记，但后面从1到2的1使2变成3，但2已经被标记，无法更新。这样就错了。所以绝对不能用于含有负权边的图。

新手常见错误

  1. 忘记初始化无穷大：如果 dist 没有初始化为很大的数，默认可能是0，导致算法认为所有顶点都离起点很近，结果全错。

  2. 忘记标记 visited：如果没标记已探索，你可能反复从同一个顶点出发更新，导致死循环或错误更新。

  3. 在更新时没检查 graph[u][v] != 0：邻接矩阵中用0表示没有路，如果忘了，就会把起点到自己的0当成一条边，导致错误更新。

  4. 把起点也加入循环 N 次：实际主循环只需 N-1 次，因为起点已经确定。如果循环 N 次，最后一次会多一次无意义查找。

  5. 误以为所有顶点都能到达：如果图不连通，有些顶点距离会保持无穷大，输出要判断 INT_MAX。

  6. 使用超大图的邻接矩阵：如果顶点数很多（比如10000个），邻接矩阵会占用大量内存，这时应该用邻接表+优先队列优化版本。

优化与扩展

上面的基础版每次找最小距离顶点都遍历所有顶点，时间复杂度是O(N²)。当顶点很多时，可以用**优先队列（小根堆）**来加速，把每次找最小距离的时间降到O(logN)，整体复杂度变成O((N+M)logN)，其中M是边数。这是竞赛中最常用的写法。感兴趣的同学可以学习“堆优化的Dijkstra”。

另外，如果图中有负权边，就不能用Dijkstra了，但可以用Bellman-Ford算法或SPFA算法。如果要求所有顶点对之间的最短路径，可以用Floyd-Warshall算法。

相关学习指引

学完Dijkstra，你可以继续探索：

  • Bellman-Ford算法：可以处理负权边，还能检测负环。
  • SPFA算法：队列优化的Bellman-Ford，效率高，但可能被卡数据。
  • Floyd-Warshall算法：简单粗暴，求所有点对最短路，O(N³)，适合小规模图。
  • 堆优化Dijkstra：竞赛中的标准写法，用 priority_queue 实现。
  • 最短路径的实际应用：导航软件、网络路由、游戏寻路等。

记住，Dijkstra是你手中的第一个“寻路神器”，但一定要记住它的使用条件——图上所有边权必须是非负数。多练几道题，你就能熟练运用它啦！

例题精讲

1单选题

使用二叉堆（优先队列）优化的Dijkstra算法的时间复杂度是？

AO(n^2)
BO(m log n)
CO(n log m)
DO(n m)
2判断题

Dijkstra算法中，如果图中存在负权边，算法仍然可以正确求出单源最短路径。

3填空题
void dijkstra(int s) {
    vector<int> dist(n, INF);
    dist[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d != dist[u]) continue;
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(___);
            }
        }
    }
}