1 基础知识

存在负权边时，使用spfa算法来求解最短路问题，它的时间复杂度为O(m)。

spfa算法求最短路问题的关键步骤：

1. 初始化距离数组dist为正无穷大，然后d[1] = 0。
2. 定义队列q，将1号结点插入到队列中。
3. 如果队列不空：弹出队头t，看看t能走到哪儿，比如t能走到x。如果dist[x] > dist[t] + edge[t][x]，则更新dist[x]，如果x不在队列中，则将x插入到队列q中。
4. 继续执行步骤3，直到队列为空。
5. dist[n]，即为1号结点到n号结点的最短距离。如果等于0x3f3f3f3f，则表示不存在最短路，输出-1。

此外，spfa算法还可以用来判断图中是否存在负回环（额外维护一个cnt数组，表示1号结点到x号结点的最短路径上边的数目，如果cnt[x] >= n，则表示图中存在负回环）。

spfa算法判断图中是否存在负回环的关键步骤：

1. 初始化cnt数组，将它们的值都设置为0。
2. 定义队列q，将1号结点、2号结点、3号结点、…、n号结点插入到队列q中。
3. 如果队列不空：弹出队头结点t，看看t能走到哪儿，比如t能走到x。如果dist[x] > dist[t] + edge[t][x]，则更新dist[x]和cnt[x]。如果cnt[x] >= n，返回true，表示图存在负回环。如果x不在队列q中，则把x插入到队列中。
4. 继续执行步骤3，直到队列为空。
5. 返回false，表示图中不存在负回环。

2 模板

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入{q.push(j);st[j] = true;}}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

3 工程化

题目1：存在负权边，求最短路。

#include <iostream>
#include <cstring>
#include <queue>using namespace std;const int N = 1e5 + 10;
int n, m;
int dist[N];
bool st[N];
vector<vector<pair<int,int>>> g(N); //first表示能走到的结点，second表示这条边的长度void spfa() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while (!q.empty()) {int t = q.front();q.pop();st[t] = false;for (auto [x, w] : g[t]) {if (dist[x] > dist[t] + w) {dist[x] = dist[t] + w;if (!st[x]) {q.push(x);st[x] = true;}}        }}if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;else cout << dist[n] << endl;return; 
}int main() {cin >> n >> m;int a, b, c;while (m--) {cin >> a >> b >> c;g[a].emplace_back(make_pair(b,c));}spfa();return 0;
}

题目2：判断图中是否存在负回环。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>using namespace std;const int N = 2010;
int n, m;
int dist[N], cnt[N];
bool st[N];
vector<vector<pair<int,int>>> g(N);//first表示下一个能走到的结点，second表示边的长度void spfa() {queue<int> q;//把n个结点都插入到队列q中for (int i = 1; i <= n; ++ i) {q.push(i);st[i] = true;}while (!q.empty()) {auto t = q.front();q.pop();st[t] = false;//看t能走到哪里for (auto [x, w] : g[t]) {if (dist[x] > dist[t] + w) {dist[x] = dist[t] + w;cnt[x] = cnt[t] + 1;if (!st[x]) {q.push(x);}if (cnt[x] >= n) {cout << "Yes" << endl;return;}}}}cout << "No" << endl;return;
}int main() {cin >> n >> m;int a, b, c;for (int i = 0; i < m; ++i) {cin >> a >> b >> c;g[a].emplace_back(make_pair(b,c));}spfa();return 0;
}