ztrztr 的博客 - 最短路
type: channel
link: https://typecho.ztrztr.top/tag/e6-9c-80-e7-9f-ad-e8-b7-af/
items: SPFA 学习笔记

SPFA 学习笔记
type: item
date: 2024-06-02T18:48:49+08:00
description: SPFA学习笔记SPFA，他死了！——某次 noi T1 的出题人。感觉和 DIJ 很像。使用范围：负边权，判断负环，随机图不适用于构造图。容易超时。思路：对于出发的点，向所有可以到达，并且没到达过的点的边都进行松弛（见 图论——dijkstra），将松弛的点入队，注意是队列不是优先队列。继续重复上面的操作，直到队列为空。#include <bits/stdc++.h> using namespace std; /* spfa. */ #define MAX 100005 #define node int #define INF 0x7fffffff vector <long long> edge[MAX], edgeValue[MAX]; long long n, m, minDistance[MAX], visited[MAX]; node start; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> start; for (int i = 1; i <= m; i ++) { int from, to, value; cin >> from >> to >> value; edge[from].push_back(to); edgeValue[from].push_back(value); } //This is input. for (int i = 1; i <= n; i ++) minDistance[i] = INF; minDistance[start] = 0; visited[start] = 1; queue <int> nodeQueue; nodeQueue.push(start); // cout << minDistance[start] << "\n"; //Push the first node. while (!nodeQueue.empty()) { int lastNode = nodeQueue.front(); nodeQueue.pop(); visited[lastNode] = 0; for (int i = 0; i < edge[lastNode].size(); i ++) { int nowNode = edge[lastNode][i]; // cout << lastNode << " " << nowNode << " " << minDistance[nowNode] << " " << minDistance[start] << " \n"; if (minDistance[nowNode] > minDistance[lastNode] + edgeValue[lastNode][i]) { minDistance[nowNode] = minDistance[lastNode] + edgeValue[lastNode][i]; if (visited[nowNode] == 0) { visited[nowNode] = 1; nodeQueue.push(nowNode); } } } //Get the min distance of ${start} and other nodes. } for (int i = 1; i <= n; i ++) { cout << minDistance[i] << " "; } //Print minDistance. return 0; }除了最短路，我们还可以在判断负环的时候运用spfa算法。而且在判断负环的时候，spfa的效率是 $O(n)$ 的。（不确定，有没有大佬来指点一下）思路：如果入队次数大于 n-1，有负环，否则没有注意切记设置初始值=0的时候要放在初始化后面！负边权，适合spfa单源最短路，求和的适合dijkstra求路径的适合floyd