题目描述
spfa 方法判断负环
算法1
spfa
引入虚拟源点,参考呆呆佬的解说
dist[x]
记录的是虚拟源点到 x
的最短距离
cnt[x]
记录的是虚拟源点到 x 的最短路一共有多少条边
dist[] 数组没有被初始化为 INF 最大值,
那么存在负环的时候,一定会进行 dist[]
数组的更新
则只要 cnt[] >=n
了,就说明从源点到该点至少经过了 n 条边,则说明至少经过了 n+1 个点,则说明有点被重复使用了,即为存在负环.
这题求的是判断图中的负环,为了防止图不连通,所以初始时将所有的点都加入队列,进行更新。
时间复杂度
一般 $O(m)$
最坏 $O(n*m)$
其中 n 为点数, m 为边数
参考文献
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int n,m;
static int N = 2010;
static int M=10010;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int idx;
static int [] dist=new int[N];
static int[]cnt=new int[N];
static boolean[] st=new boolean[M];
static int INF=0x3f3f3f3f;
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
public static boolean spfa(){
Queue<Integer> queue = new LinkedList<Integer>();
//将所有点进入队列
for(int i = 1;i <= n;i++)
{
queue.add(i);
st[i] = true;
}
while(queue.size()>0){
int t=queue.poll();
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];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n){
return true;
}
if(!st[j]){
queue.offer(j);
st[j]=true;
}
}
}
}
return false ;
}
public static void main(String[] args) throws IOException {
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String[] strs=reader.readLine().split(" ");
n=Integer.parseInt(strs[0]);
m=Integer.parseInt(strs[1]);
Arrays.fill(h,-1);
for(int i=0;i<m;i++){
strs=reader.readLine().split(" ");
int a=Integer.parseInt(strs[0]);
int b=Integer.parseInt(strs[1]);
int c=Integer.parseInt(strs[2]);
add(a,b,c);
}
if (spfa()){
System.out.println("Yes");
}else{
System.out.println("No");
}
reader.close();
}
}