Java最短路SPFA
时间: 2024-02-23 22:32:22 浏览: 15
SPFA算法是一种求解最短路的算法,它是基于Bellman-Ford算法的改进版。与Bellman-Ford算法不同的是,SPFA算法将每个节点的更新顺序改为了队列中的任意顺序。这样可以减少不必要的松弛操作,从而提高算法的效率。以下是Java实现最短路SPFA算法的代码:
```java
import java.util.*;
public class SPFA {
private static final int INF = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //节点数
int m = sc.nextInt(); //边数
int s = sc.nextInt(); //起点
int t = sc.nextInt(); //终点
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
graph.get(u).add(new Edge(v, w));
graph.get(v).add(new Edge(u, w));
}
int[] dist = new int[n];
Arrays.fill(dist, INF);
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(s);
visited[s] = true;
dist[s] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
visited[u] = false;
for (Edge e : graph.get(u)) {
int v = e.to;
if (dist[v] > dist[u] + e.weight) {
dist[v] = dist[u] + e.weight;
if (!visited[v]) {
visited[v] = true;
queue.offer(v);
}
}
}
}
System.out.println(dist[t]);
}
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
}
```