SPFA單源最短路算法

适用情況

與 Dijkstra 算法類似，隻不過該算法可以判斷是否存在負環（不能處理負環）。目的是求單源最短路。

時間複雜度為 O(nm)

該算法可由 Dijkstra 算法替換使用，優于其在于可判斷負環。

思想

Bellman-Ford 的改進版。（下述代碼采用領接表存儲資料）

①【初始化（隊列、标記數組等）】建立一個隊列，将源點加入隊列中并做相關處理（加标記、統計入隊次數），然後循環直到隊列為空。

②【周遊相鄰點并更新資料】循環中，每次取隊首頂點（做标記），然後周遊與之相鄰的所有點。比較 此隊首頂點到源點的距離加上其相鄰點之間的距離（即為隊首頂點到源點距離+隊首頂點到與之相鄰點的距離和） 和 相鄰點到源點的距離（即源點到與之相鄰點的原始值）大小，更新相鄰點到源點的距離使之最小。

③【入隊并判負環】找到可以更新後，如果沒有标記此點則标記再入隊，并統計入隊次數（如果入隊次數大于等于 n 時則表示存在負環）

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static class edge{
		int to,v,nex;
	}
	static int M = 200005;
	static int N = 20005;
	static int cnt = 0;
	static edge[] e = new edge[M];
	
	static int n, m;
	static int[] h = new int[N];//父節點集
	static int[] dis = new int[N];//源點到i的距離
	static boolean[] f = new boolean[N];//标記是否入隊
	static int[] k = new int[N];//入隊次數
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		n = cin.nextInt();//頂點數
		m = cin.nextInt();//邊數
		// a 到 b 的距離為 c
		for(int i=0;i<m;i++) {
			int a = cin.nextInt();
			int b = cin.nextInt();
			int c = cin.nextInt();
			add(a,b,c);//此為有向圖
		}
		SPFA(1);
		for(int i=2;i<=n;i++) {
			System.out.println(dis[i]);
		}
	}

	private static void SPFA(int s) {
		Queue<Integer> q = new LinkedList<>();
		Arrays.fill(dis, Integer.MAX_VALUE);
		Arrays.fill(f, false);
		Arrays.fill(k, 0);
		
		q.add(s);
		dis[s] = 0;
		f[s] = true;
		while(!q.isEmpty()) {
			int t = q.poll();
			f[t] = false;
			
			for(int i=h[t]; ;i=e[i].nex) {
				if(e[i] == null)break;
				
				int temp = e[i].to;
				if(dis[temp] > dis[t] + e[i].v) {
					dis[temp] = dis[t] + e[i].v;
					
					if(f[temp] == false) {
						q.add(temp);
						f[temp] = true;
						if(++k[temp] >= n) {//判斷是否存在負環
							System.out.println("存在負環");
							return ;
						}
					}
				}
			}
		}
	}

	private static void add(int a, int b, int c) {
		e[++cnt] = new edge();// cnt從1開始（點編号）
		e[cnt].to = b;
		e[cnt].v = c;
		e[cnt].nex = h[a];
		h[a] = cnt;
	}
}
           

如有錯誤或不合理的地方，敬請指正~

加油！！