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

定义

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

时间复杂度：如果图是随机生成的，时间复杂度为O(K·M)，K是某个常数；最坏情况下时间复杂度为O(N·M)。

原理

用dis数组记录源点到有向图上任意一点的距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：

1. 队首x出队。
2. 遍历所有以队首为起点的有向边(x,i)，若dis[x] + w(x,i) < dis[i]，则更新dis[i]。
3. 如果点i不在队列中，则i入队。
4. 若队列为空，结束，否则跳到1。

代码

洛谷P3371

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

const int MAXN = 10005;
const int MAXM = 500005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int dest, next, weight;
} edges[MAXM];
int head[MAXN];
int edges_cnt;
int dis[MAXN];   // 源点到每个点的最短距离
bool inq[MAXN];  // 某个点是否在队列内
int n, m, s;

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;
}

void spfa(int src) {
    memset(dis, 0x3f, sizeof(dis));
    memset(inq, 0, sizeof(inq));
    dis[src] = 0;
    queue<int> q;
    q.emplace(src);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        inq[top] = false;
        for (int i = head[top]; i; i = edges[i].next) {
            int dest = edges[i].dest;
            int weight = edges[i].weight;
            if (dis[top] + weight < dis[dest]) {
                dis[dest] = dis[top] + weight;
                if (!inq[dest]) {
                    q.emplace(dest);
                    inq[dest] = true;
                }
            }
        }
    }
}

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d%d", &n, &m, &s);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
    }
    spfa(s);
    for (int node = 1; node <= n; ++node) {
        printf("%d ", dis[node] < INF ? dis[node] : INT_MAX);
    }
    putchar('\n');

    return 0;
}

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