经典图算法：Dijkstra 算法

什么是 Dijkstra 算法？

Dijkstra 算法是一种用于计算图中 单源最短路径 的经典算法。它适用于所有边权都为 非负数 的图。

给定一个图和一个源点 s，Dijkstra 算法可以计算出 s 到所有其他节点的最短路径长度。

算法思想

Dijkstra 算法基于贪心策略。它维护一个从源点 s 出发的距离集合 dist，其中 dist[v] 表示当前已知的从 s 到 v 的最短距离。

1. 初始化:

   • dist[s] = 0。
   • 对于所有其他节点 v，dist[v] = ∞。
   • 创建一个集合 S，用于存放已经找到最短路径的顶点。初始时 S 为空。

2. 迭代: 重复 n 次（n 是节点数）： a. 从尚未在 S 中的顶点中，选择一个 dist 值最小的顶点 u。 b. 将 u 加入 S。 c. 对于 u 的每一个邻居 v，进行 松弛操作 (Relaxation)： 如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] = dist[u] + weight(u, v)。

堆优化

朴素的 Dijkstra 算法每次选择最小 dist 值的节点需要 O(n) 的时间，总时间复杂度为 O(n²)。我们可以使用 优先队列（最小堆） 来优化这个过程。

1. 初始化:

   • dist 数组初始化同上。
   • 创建一个优先队列 pq，并将 (0, s)（距离，节点）存入。

2. 循环: 当 pq 不为空时： a. 从 pq 中取出距离最小的节点 u（pq.top()）。 b. 如果 u 已经被访问过（即已在 S 中），则跳过。 c. 标记 u 为已访问。 d. 对 u 的所有邻居 v 进行松弛操作，如果 dist[v] 被更新，则将 (dist[v], v) 加入 pq。

C++ 代码实现 (堆优化)

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

const int INF = std::numeric_limits<int>::max();

void dijkstra(int s, int n, const std::vector<std::vector<std::pair<int, int>>>& adj) {
    std::vector<int> dist(n + 1, INF);
    dist[s] = 0;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({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 weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // 打印结果
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            std::cout << "Node " << i << " is unreachable from " << s << std::endl;
        } else {
            std::cout << "Shortest distance from " << s << " to " << i << " is " << dist[i] << std::endl;
        }
    }
}

复杂度分析

• 朴素实现: O(V²)
• 堆优化实现: O(E log V)，其中 V 是顶点数，E 是边数。这是目前最常用的实现方式。

Dijkstra 算法是图论中最重要的算法之一，是解决许多最短路问题的基础。