spfa−三种语言实现全解析
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
思路
1.时间复杂度方面
一般O(m) 最坏O(nm)
2.算法原理
Dijkstra算法的一点更新，后续邻点波动更新的思路非常好，但是我们在Bellman_ford那里的总结得知，因为
st[i]的锁定，导致出现连环错误。那么我们该如何优化它无法在负权边使用的遗憾？
答案就是：我们干脆就不锁定了！让这个bool值就当成一个判断是不是在队列的标志，如果它在队列里
我们更新完就不添加它，反正它后续还会出现，如果没出现就继续加，类似BFS一样。
稀疏图我们还用邻接表，而且由于利用BFS的思想，甚至不需要每次找最短点了，效率比Dijkstra大多数时候
反而更好
一旦更小更新距离还是dist[x] = dist[t] + w[i];
3.算法细节
判断负环存在的方法
bellman_ford可以用于负环存在的时候，因为反正刷新次数已经定了，肯定没法出现无穷或者死循环
那么有没有什么方法能判断负环是不是存在呢？（废话，题目都是spfa判断最短路了）
spfa判断负环的原理：
首先我们肯定不能按从起点遍历（万一负环就不在这条线怎么办？）
直接全部点放入队列并置st[i]为true，进行依次判断距离然后更新操作，只不过这次更新我们设置
了一个cnt数组，每更新一次对应点的更新次数就刷新。一共n个点，最远的点也不过n-1条边，如果
一个点更新了超过这个数，不用问那只能是在走入快乐的负环里蹦极了
这个算法的代码非常简单，就不写代码细节了
1. java 使用容器
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
public class Main {
static int N = 100010, n, m, idx;
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] h = new int[N];
static int[] w = new int[N];
static boolean[] st = new boolean[N];
static int[] d = new int[N];
static void add(int x, int y, int z) {
e[idx] = y;
ne[idx] = h[x];
w[idx] = z;
h[x] = idx++;
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static void spfa() {
d[1] = 0;
LinkedList<Integer> q = new LinkedList<Integer>();
q.add(1);
while (!q.isEmpty()) {
int father = q.remove();
st[father] = false;
for (int i = h[father]; i != -1; i = ne[i]) {
int son = e[i];
if (d[son] > d[father] + w[i]) {
d[son] = d[father] + w[i];
if (!st[son]) {
q.add(son);
st[son] = true;
}
}
}
}
if (d[n] >= 0x3f3f3f3f / 2) System.out.println("impossible");
else System.out.println(d[n]);
}
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
Arrays.fill(d, 0x3f3f3f3f);
Arrays.fill(h, -1);
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for (int i = 0; i < m; i++) {
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int w = Integer.parseInt(s2[2]);
add(a, b, w);
}
spfa();
}
}
2. java 手写队列
import java.util.*;
public class Main {
static int N = 100010, n, m, idx;
static int e[] = new int [N];
static int ne[] = new int [N];
static int h[] = new int [N];
static int w[] = new int [N];
static int d[] = new int [N];
static int q[] = new int [2*N];
static boolean st[] = new boolean [N];
public static void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
public static void spfa() {
int hh = 0, tt = 0;
q[hh] = 1;
Arrays.fill(d, 0x3f3f3f3f);
d[1] = 0;
st[1] = true;
while(hh <= tt){
int t = q[hh++];
st[t] = false;
for(int i=h[t]; i!=-1; i=ne[i]){
int j = e[i];
if (d[j] > d[t] + w[i]){
d[j] = d[t] + w[i];
if (!st[j]) {
q[++tt] = j;
st[j] = true;
}
}
}
}
if (d[n] > 0x3f3f3f3f / 2) System.out.println("impossible");
else System.out.println(d[n]);
}
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
while(m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int w = sc.nextInt();
add(a, b, w);
}
spfa();
}
}
3. python3 spfa最短路(使用Queue)
N = int(1e5+10)
h = [-1] * N
e = [0] * N
ne = e.copy()
w = e.copy()
d = [0x3f3f3f3f] * N
st = [False] * N #维护一个点是否已经在队列中
idx = 0
def add(a, b, c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx += 1
def spfa():
import queue
q = queue.Queue()
d[1] = 0
q.put(1)
st[1] = True
while q.qsize():
x = q.get()
st[x] = False
i = h[x]
while i != -1:
y = e[i]
if d[y] > d[x] + w[i]:
d[y] = d[x] + w[i]
if not st[y]:
q.put(y)
st[y] = True
i = ne[i]
return d[n]
if __name__ == '__main__':
n, m = map(int, input().split())
for i in range(m):
a, b, c = map(int, input().split())
add(a, b, c)
if spfa() >= 0x3f3f3f3f // 2: print('impossible')
else: print(spfa())
4. python3 spfa最短路(手写队列)
N = 100010
h = [-1]*N
e = [0]*N
ne = [0]*N
idx = 0
st = [False]*N
dist = [0x3f3f3f3f]*N
w = [0]*N
def add(a,b,c):
global idx
e[idx] = b
w[idx] = c
ne[idx] = h[a]
h[a] = idx
idx += 1
def spfa():
dist[1] = 0
hh,tt = 0,-1
q = []
q.append(1)
tt += 1
st[1] = True
while hh <= tt:
t = q[hh]
hh += 1
st[t] = False
i = h[t]
while i != -1:
j = e[i]
if dist[j] > dist[t] + w[i]:
dist[j] = dist[t] + w[i]
if not st[j]:
q.append(j)
tt += 1
st[j] = True
i = ne[i]
return dist[n]
n,m = map(int,input().split())
while m:
m -= 1
a,b,c = map(int,input().split())
add(a,b,c)
t = spfa()
if t > 0x3f3f3f3f / 2:
print("impossible")
else:
print(t)
5. python3 spfa求负环(手写队列)
N = 2010
M = int(1e4+10)
d = [0x3f3f3f3f] * N
# 负环可能出现在非起点能到达的地方，故全放入
st = [True] * N
cnt = [0] * N
# 邻接表
h = [-1] * N
e = [0] * M
ne = e.copy()
w = e.copy()
idx = 0
q = []
def add(a, b, c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx += 1
def spfa():
#所有点最开始均在队列中
q = list(range(1,n+1))
hh,tt = 0, n - 1
d[1] = 0
while hh <= tt:
x = q[hh]
hh += 1
st[x] = False
i = h[x]
while i != -1:
j = e[i]
if d[j] > d[x] + w[i]:
d[j] = d[x] + w[i]
cnt[j] = cnt[x] + 1
if cnt[j] >= n: return True
if not st[j]:
q.append(j)
tt += 1
st[j] = True
i = ne[i]
return False
if __name__ == '__main__':
n, m = map(int, input().split())
for i in range(m):
a, b, c = map(int, input().split())
add(a, b, c)
if spfa(): print('Yes')
else: print('No')
6. C++ spfa求最短路
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], ne[N], e[N], w[N], idx;
int n, m;
int dist[N];
//与dijkstra不同，spfa存储的是是否在队列的bool值
//换而言之，更新过的点若在队列，就为true，会动态变化
//而dijkstra是当最小点将相邻点均更新完，那么我再也用不到它了
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
//入队则置1
st[1] = true;
while(q.size())
{
auto t = q.front();
q.pop();
//一旦出队则为false
st[t] = false;
for(int i=h[t]; i!=-1; i=ne[i])
{
int x = e[i];
if(dist[x] > dist[t] + w[i])
{
dist[x] = dist[t] + w[i];
if(!st[x])
{
//未入队则入队，已入队只需要更新值
st[x] = true;
q.push(x);
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return false;
else return true;
}
int main()
{
int a, b, c;
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
scanf("%d%d%d", &a, &b, &c);
add(a,b,c);
}
if(spfa()) cout << dist[n] << endl;
else puts("impossible");
return 0;
}
7. C++判断负环
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 1e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool spfa()
{
queue <int> q;
//由于题目没说是从1开始的环，故我们需要全部入队并置true
for(int i=1; i<=n; i++) q.push(i), st[i] = true;
while(q.size())
{
int t = q.front();
//出队则置为false
q.pop();
st[t] = false;
for(int i=h[t]; i!=-1; i=ne[i])
{
int x = e[i];
if(dist[x] > dist[t] + w[i])
{
dist[x] = dist[t] + w[i];
//每次刷新，需要加上上一个点经过的边数和到自己这条边
cnt[x] = cnt[t] + 1;
//若经过的边数大于等于n，则说明经过大于等于n+1个点
//但是整个图只有n个点，经过n+1以上点还可以到，说明有负权边
if(cnt[x] >= n) return true;
//未在队列的点，就继续加入队列，并遍历之后的点
//spfa原则：一点刷新，它后面的点都需要刷新
if(!st[x])
{
q.push(x);
st[x] = true;
}
}
}
}
//出while
return false;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b ,c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}
8. java 判断负环
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
public class Main {
static int N = (int) 1e5 + 10, M = 2010, idx, n, m;
static final int MAX_VALUE = 0x3f3f3f3f;
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] w = new int[N];
static int[] h = new int[M];
static int[] cnt = new int[M];
static int[] d = new int[M];
static boolean[] st = new boolean[M];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
static void spfa() {
d[1] = 0;
LinkedList<Integer> q = new LinkedList<>();
Arrays.fill(st, true);
for (int i = 1; i <= n; i++) q.add(i);
while (!q.isEmpty()){
int x = q.remove();
st[x] = false;
for (int i = h[x]; i != -1; i=ne[i]) {
int j = e[i];
if(d[j] > d[x] + w[i]){
cnt[j] = cnt[x] + 1;
if(cnt[j] > n - 1){
System.out.println("Yes");
return;
}
d[j] = d[x] + w[i];
if(!st[j]){
q.add(j);
st[j] = true;
}
}
}
}
System.out.println("No");
}
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
Arrays.fill(h, -1);
Arrays.fill(d, MAX_VALUE);
for (int i = 0; i < m; i++) {
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
add(a, b, c);
}
spfa();
}
}
