Dijkstra

Dijkstra 算法是（在数据结构优化情况下）在​O(mlog_2n)时间复杂度下的单源最短路径算法。

P4779 【模板】单源最短路径（标准版）模板代码：

//
// Created by asdf on 1/29/2024.
//
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;

const int N = 1e5 + 10, M = 2e5 + 10;
int dis[N];
bool processed[N];
vector<ii> adj[N];

void dijkstra(int start, int total_node) {
    priority_queue<ii, vector<ii>,greater<>> pq; // min-heap
    // initialize
    fill_n(dis, N,INT_MAX);

    // starting node
    dis[start] = 0;
    pq.emplace(0, start);

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

        //update processed array
        if (processed[u])continue;
        processed[u] = true;

        for (auto &edge: adj[u]) {
            int v = edge.second;
            int n_dist = edge.first;

            // if there is a shorter path to v through u
            if (dis[u] + n_dist < dis[v]) {
                dis[v] = dis[u] + n_dist;
                pq.emplace(dis[v],v);// push the new distance to pq
            }
        }
    }
}

int main() {
    int n,m,s;
    cin>>n>>m>>s;
    for (int i = 0; i < m; ++i) {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].emplace_back(w,v);
    }
    dijkstra(s,n);
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<' ';
    }
    return 0;
}

来自2025-1-25的update：

好久没碰算法了重新搓了一遍，发现上面的实现还挺别致的。oi wiki 还有 usaco.guide 上面的实现都是又用结构体定义edge和node：

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

这里我们的 pair<int,int> 既是node也是edge，以下是更新注释后的代码，注意两个DEF（definition)：

/* https://www.luogu.com.cn/problem/P4779
 * Created by: Friedforks
 * Date: 2025-01-25
 */
#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> ii;

const int MAXN = 1e5 + 5, M = 2e5 + 5;
int dis[MAXN];
bool processed[MAXN];
// DEF 1:the pair ii serve as edge  <weight, node number>
vector<ii> adj[MAXN];

void dijkstra(int start, int total_node) {
    // DEF 2:here the pair ii serve as node <distance, node number>
    priority_queue<ii, vector<ii>, greater<>> pq; // min-heap
    // initialize the distance all to be infinity
    fill_n(dis, MAXN, INT_MAX);

    // starting node
    dis[start] = 0; // distance to itself is 0
    pq.emplace(0, start);

    while (!pq.empty()) {
        const int u = pq.top().second; // add next node to pq

        // update processed array
        if (processed[u])
            continue;
        processed[u] = true;

        for (auto &edge : adj[u]) {
            int v = edge.second;
            const int weight = edge.first;

            // if there is a shorter path to v through u
            if (dis[u] + weight < dis[v]) {
                // update the shorter distance
                dis[v] = dis[u] + weight;
                // check if already processed
                if (!processed[v]) {
                    pq.emplace(dis[v], v); // push the new distance to pq
                }
            }
        }
    }
}

int main() {
    int n, m, s; // n node, m edges, s start node
    cin >> n >> m >> s;
    // input
    for (int i = 0; i < m; i++) {
        int u, v, w; // u -> v with weight w
        cin >> u >> v >> w;
        adj[u].emplace_back(w, v);
    }
    dijkstra(s, n);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << ' ';
    }
    return 0;
}