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)