Dijkstra 算法简介与 C++ 实现模板

一、算法概述

Dijkstra 算法是一种用于解决单源最短路径问题的经典算法。给定一个带权有向图或无向图，算法可以求出从源点到图中每个顶点的最短路径长度。其核心思想是贪心策略：每次选择当前距离源点最近的未处理节点，并更新其邻居的最短路径。

特点

  1. 适用于非负权重图（边权必须 ≥ 0）。
  2. 可以用于有向图或无向图。
  3. 时间复杂度：
    • 使用数组实现：(O(V^2))
    • 使用优先队列（最小堆）实现：(O(E \log V))，其中 (V) 为顶点数，(E) 为边数。

二、算法原理

  1. 初始化源点 dist[source] = 0，其他顶点距离为无穷大。
  2. 将所有顶点加入未处理集合（或使用优先队列维护）。
  3. 每次从集合中选取距离源点最小的顶点 u。
  4. 遍历 u 的邻居 v，尝试松弛边 (u, v)： [ \text{dist}[v] = \min(\text{dist}[v], \text{dist}[u] + \text{weight}(u, v)) ]
  5. 重复步骤 3-4，直到所有顶点处理完。

三、C++ 模板实现

这里给出使用 优先队列（min-heap） 的高效实现：

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;  // 定义无穷大
const int MAXN = 100005;

struct Edge {
    int to, weight;
};

vector<Edge> adj[MAXN];  // 邻接表存储图
int dist[MAXN];          // 源点到各点最短距离
bool visited[MAXN];      // 标记是否已处理

void dijkstra(int source, int n) {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }

    dist[source] = 0;
    // 优先队列存储 pair<距离, 节点>
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;  // 已处理则跳过
        visited[u] = true;

        for (auto &edge : adj[u]) {
            int v = edge.to, w = edge.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // n个顶点，m条边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // 若是无向图，加上这一行
        // adj[v].push_back({u, w});
    }

    int source;
    cin >> source;

    dijkstra(source, n);

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }

    return 0;
}

Updated: