一、算法概述

迪杰斯特拉算法（Dijkstra's Algorithm）是由荷兰计算机科学家 Edsger W. Dijkstra 于 1959 年提出的经典单源最短路径算法。它用于求解边权非负的带权图中，从单个源点到所有其他节点的最短路径。该算法是图论中最重要、应用最广泛的算法之一。

二、核心思想

Dijkstra 算法采用贪心策略：

1. 维护一个集合 $S$，存放已经确定最短距离的节点；维护距离数组 $dist[]$，$dist[v]$ 表示从源点到 $v$ 的当前最短距离估计值
2. 初始时，$dist[source] = 0$，其余为 $+\infty$
3. 每次从尚未确定的节点中选出 $dist$ 值最小的节点 $u$，将 $u$ 加入 $S$（即确定 $u$ 的最短距离）
4. 对 $u$ 的所有出边 $(u, v, w)$ 执行松弛操作：若 $dist[u] + w < dist[v]$，则更新 $dist[v]$
5. 重复步骤 3-4，直到所有节点都进入 $S$

为什么正确？因为在边权非负的前提下，当前距离最小的未确定节点，不可能通过其他未确定节点获得更短的路径——这是贪心正确性的保证。

三、算法步骤/伪代码

Dijkstra(图 G, 源点 s):
    dist[1..V] = +∞
    dist[s] = 0
    优先队列 pq，按 dist 排序，初始放入 (dist[s], s)

    while pq 非空:
        (d, u) = pq.top(), pq.pop()
        if d > dist[u]:  continue   // 过时数据，跳过

        for 每条出边 (u, v, 权重 w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pq.push((dist[v], v))

    return dist

关键数据结构

• dist[]：距离数组
• priority_queue（最小堆）：高效取出当前距离最小的节点，优化到 $O(\log V)$ 每次
• visited[]（或等效判断）：标记节点是否已确定最短距离。用优先队列时，可用 d > dist[u] 来替代显式标记

四、C++ 代码实现

完整可运行的 Dijkstra 实现，使用优先队列优化，包含邻接表建图和结果输出。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, int> P; // (距离, 节点编号)

class Dijkstra {
private:
    int V;                          // 节点数
    vector<vector<pair<int, ll>>> adj; // 邻接表: adj[u] = {(v, w), ...}

public:
    Dijkstra(int n) : V(n), adj(n) {}

    // 添加有向边 u -> v，权重为 w
    void addEdge(int u, int v, ll w) {
        adj[u].push_back({v, w});
    }

    // 返回源点 src 到所有节点的最短距离
    // 不可达节点的距离为 LLONG_MAX
    vector<ll> shortestPath(int src) {
        vector<ll> dist(V, LLONG_MAX);
        dist[src] = 0;

        // 最小堆，pair<距离, 节点>
        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push({0, src});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            // 过时数据，跳过
            if (d > dist[u]) continue;

            // 松弛所有邻接边
            for (auto& edge : adj[u]) {
                int v = edge.first;
                ll w = edge.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    }

    // 返回源点到目标节点的最短距离
    ll shortestPathTo(int src, int target) {
        return shortestPath(src)[target];
    }

    // 还原从 src 到 target 的最短路径（非必须，演示用）
    vector<int> getPath(int src, int target) {
        vector<ll> dist(V, LLONG_MAX);
        vector<int> prev(V, -1);
        dist[src] = 0;

        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push({0, src});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            if (u == target) break; // 提前终止

            for (auto& edge : adj[u]) {
                int v = edge.first;
                ll w = edge.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        // 回溯还原路径
        vector<int> path;
        if (dist[target] == LLONG_MAX) return path; // 不可达
        for (int cur = target; cur != -1; cur = prev[cur])
            path.push_back(cur);
        reverse(path.begin(), path.end());
        return path;
    }
};

// ==================== 主函数 ====================
int main() {
    // 构建一个有向带权图
    // 示例图（6个节点 0~5）：
    //   0 ---(2)---> 1 ---(5)---> 3
    //   |           / \           |
    //  (4)      (8)   (2)       (3)
    //   |       /       \        |
    //   2 <---(1)---      \--->  5
    //              \            /
    //               \---(6)---/
    //                    4
    Dijkstra dijk(6);

    dijk.addEdge(0, 1, 2);
    dijk.addEdge(0, 2, 4);
    dijk.addEdge(1, 2, 1);
    dijk.addEdge(1, 3, 5);
    dijk.addEdge(1, 4, 8);
    dijk.addEdge(2, 1, 1);
    dijk.addEdge(3, 5, 3);
    dijk.addEdge(4, 3, 2);
    dijk.addEdge(4, 5, 6);

    int src = 0;
    auto dist = dijk.shortestPath(src);

    cout << "========== Dijkstra 最短路径 ==========" << endl;
    cout << "源点: " << src << endl;
    for (int i = 0; i < 6; ++i) {
        cout << src << " -> " << i << " : ";
        if (dist[i] == LLONG_MAX)
            cout << "不可达" << endl;
        else
            cout << dist[i] << endl;
    }

    // 还原并打印一条路径
    int target = 5;
    cout << "\n从 " << src << " 到 " << target << " 的最短路径: ";
    auto path = dijk.getPath(src, target);
    if (path.empty()) {
        cout << "不可达" << endl;
    } else {
        cout << "总距离 = " << dist[target] << endl << "路径: ";
        for (int i = 0; i < (int)path.size(); ++i) {
            if (i > 0) cout << " -> ";
            cout << path[i];
        }
        cout << endl;
    }

    return 0;
}

五、复杂度分析

• 时间复杂度：$\mathbf{O((V + E) \log V)}$

  • 每个节点最多入堆一次（实际上可能多次，但有效的 pop 只有 $V$ 次）：$O(V \log V)$
  • 每条边可能触发一次松弛和入堆操作：$O(E \log V)$
  • 合计：$O((V + E) \log V)$

• 空间复杂度：$\mathbf{O(V + E)}$

  • 邻接表：$O(V + E)$
  • dist 数组 + 优先队列：$O(V)$

如果不使用优先队列（暴力枚举最小值），时间复杂度为 $O(V^2)$，适用于稠密图（$E \approx V^2$）。

六、应用场景

场景	说明
导航系统	GPS 路径规划（非负距离）
网络路由	OSPF 协议中的最短路径计算
交通规划	计算城市间的最短出行距离或时间
游戏AI	寻路算法的基础（如 A* 算法基于 Dijkstra）
通信网络	计算最小时延路径
物流/配送	最短运输路线规划

限制：Dijkstra 不能处理负权边。对于含负权边的图，应使用 Bellman-Ford 算法或 SPFA。

七、经典例题

最短路径模板题

题目描述：给定一个 $n$ 个节点、$m$ 条有向边的带权图，求从节点 $1$ 到节点 $n$ 的最短距离。保证边权非负。

上述代码即为通用模板。使用时只需：

1. 读入 $n, m$
2. 循环读入 $m$ 条边并用 addEdge(u-1, v-1, w) 建图
3. 调用 shortestPath(0) 获取距离数组
4. 输出 dist[n-1]

以下是完整的模板题代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

int main() {
    int n, m;
    cin >> n >> m;  // n 个节点，m 条边

    vector<vector<pair<int, ll>>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        --u; --v; // 转为 0-indexed
        adj[u].push_back({v, w});
    }

    vector<ll> dist(n, LLONG_MAX);
    dist[0] = 0;  // 源点为节点 1（0-indexed 为 0）
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            ll w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << (dist[n - 1] == LLONG_MAX ? -1 : dist[n - 1]) << endl;
    return 0;
}

测试输入：

4 5
1 2 2
1 3 6
2 3 3
2 4 5
3 4 1

预期输出：6（最短路径为 1→2→3→4，距离为 2+3+1=6）