图论 - 单源最短路径（Dijkstra）

定义

Dijkstra算法可以求解带权有向图上某个点到其余点的最短路径距离，不支持负权边。

时间复杂度：朴素法的时间复杂度为$O(N^2)$，加上堆优化以后时间复杂度为$O((N + M)log_2(N))$。

原理

Dijkstra的流程如下：（白点——未确定最短路径的点 黑点——已确定最短路径的点）

1. 初始化dis[src] = 0，其余结点的值为INF。
2. 找一个dis值最小的白点x，把x变成黑点。
3. 遍历x的所有出边(x,y,z)，若dis[x] + z < dis[y]，则更新dis[y]。
4. 如果所有点都成为黑点，结束，否则跳到2。

正确性：当所有边长都是非负数的时候，全局最小值不可能再被其他结点更新。所以在第2步中找出的白点x必然满足dis[x]是起点到x的最短路径。我们不断选择全局最小值进行标记和拓展，最终可以得到起点到每个结点的最短路径长度。

代码

洛谷P4779

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <climits>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int n, m, s;
const int MAXN = 100005;
const int MAXM = 200005;
int head[MAXN];
struct Edge {
    int dest, weight, next;
} edges[MAXM];
int edges_cnt = 0;
int dis[MAXN];
bool visited[MAXN];

void addEdge(int src, int dest, int weight) {
    ++edges_cnt;
    edges[edges_cnt].dest = dest;
    edges[edges_cnt].weight = weight;
    edges[edges_cnt].next = head[src];
    head[src] = edges_cnt;
}

struct QNode {
    int node, dis;

    bool operator<(const QNode& other) const {
        return dis > other.dis;
    }
};

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(visited, 0, sizeof(visited));
    priority_queue<QNode> pq;
    pq.push({s, 0});
    dis[s] = 0;
    while (!pq.empty()) {
        QNode top = pq.top();
        pq.pop();
        if (!visited[top.node]) {
            visited[top.node] = true;
            for (int i = head[top.node]; i; i = edges[i].next) {
                int dest = edges[i].dest;
                int weight = edges[i].weight;
                if (dis[top.node] + weight < dis[dest]) {
                    dis[dest] = dis[top.node] + weight;
                    if (!visited[dest]) {
                        pq.push({dest, dis[dest]});
                    }
                }
            }
        }
    }
}

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d%d", &n, &m, &s);
    while (m--) {
        int src, dest, weight;
        scanf("%d%d%d", &src, &dest, &weight);
        addEdge(src, dest, weight);
    }
    dijkstra();
    for (int node = 1; node <= n; ++node) {
        printf("%d ", dis[node]);
    }
    putchar('\n');

    return 0;
}

本文地址：https://blog.csdn.net/hcmdghv587/article/details/107599837