SPFA

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

public class SPFA {
	public static void main(String[] args) {

	}

	// 边存储所用到的变量
	static int N = 1010;
	static int cnt = 0; // 边的编号
	static int[] first = new int[N];
	static Edge[] edges = new Edge[N];
	// spfa 所用到的变量
	static int[] dis = new int[N];// 动态更新一个 dis 数组
	static int[] isV = new int[N];// 标记这个顶点是否在队列中
	static int INF = Integer.MAX_VALUE;// 表示不可达

	/**
	 * 添加边的函数
	 * 
	 * @param u 起点
	 * @param v 终点
	 * @param w 权值
	 */
	static void add(int u, int v, int w) {
		edges[++cnt] = new Edge(v, w, first[u]);
		first[u]++;
	}

	static void spfa(int x) {
		// 初始化
		Arrays.fill(dis, INF);
		dis[x] = 0;
		Queue<Integer> q = new LinkedList<>();
		q.add(x);
		isV[x] = 1;
		while (!q.isEmpty()) {
			int u = q.remove();
			isV[u] = 0;
			for (int i = first[u]; i != 0; i = edges[u].next) {// 遍历以 u 为起点的所有边
				int to = edges[i].to;
				if (dis[to] > dis[u] + edges[i].w) {
					dis[to] = dis[u] + edges[i].w;
					// 松弛成功尝试加入队列
					if (isV[i] == 0) {
						q.add(i);
						isV[i] = 1;
					}
				}
			}
		}
	}
}

/**
 * 边类 三个属性
 *
 */
class Edge {
	int to;
	int w;
	int next;

	/**
	 * @param to   终点
	 * @param w    权值
	 * @param next 下一条边
	 */
	public Edge(int to, int w, int next) {
		super();
		this.to = to;
		this.w = w;
		this.next = next;
	}

}

其中涉及到图的存储问题，请移步链式前向星 - ChuenSan - 博客园 (cnblogs.com)