使用分支限界法实现单源最短路径问题,输出s到各节点的最短路径长度及到达路径。Java代码
时间: 2024-03-23 22:43:32 浏览: 21
以下是使用分支限界法实现单源最短路径问题的Java代码,输出s到各节点的最短路径长度及到达路径:
```java
import java.util.*;
public class ShortestPath {
static int INF = Integer.MAX_VALUE;
// 存储图的邻接表表示
static Map<Integer, List<Edge>> graph = new HashMap<>();
// 存储从起点到每个节点的最短路径长度
static int[] dist;
// 存储从起点到每个节点的最短路径
static List<List<Integer>> path;
static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
// 分支限界法求解单源最短路径问题
static void shortestPath(int s) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{s, 0});
while (!pq.isEmpty()) {
int[] node = pq.poll();
int u = node[0], d = node[1];
if (d > dist[u]) continue;
for (Edge e : graph.getOrDefault(u, new ArrayList<>())) {
int v = e.to, w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
// 更新路径
path.set(v, new ArrayList<>(path.get(u)));
path.get(v).add(v);
pq.offer(new int[]{v, dist[v]});
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入节点数和边数
int n = sc.nextInt();
int m = sc.nextInt();
// 初始化dist和path数组
dist = new int[n];
path = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
dist[i] = INF;
path.add(new ArrayList<>());
}
// 输入边的起点、终点、权重
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
if (!graph.containsKey(u)) {
graph.put(u, new ArrayList<>());
}
graph.get(u).add(new Edge(v, w));
}
// 输入起点
int s = sc.nextInt();
// 起点到自身的距离为0
dist[s] = 0;
path.get(s).add(s);
// 分支限界法求解单源最短路径问题
shortestPath(s);
// 输出s到各节点的最短路径长度及到达路径
for (int i = 0; i < n; i++) {
System.out.print("节点" + i + "的最短路径长度为:" + dist[i] + ",路径为:");
for (int j : path.get(i)) {
System.out.print(j + " ");
}
System.out.println();
}
}
}
```
示例输入:
```
6 10
0 1 10
0 4 15
1 2 15
1 3 2
2 5 5
3 2 1
3 5 12
4 5 10
4 3 5
5 0 6
0
```
示例输出:
```
节点0的最短路径长度为:0,路径为:0
节点1的最短路径长度为:10,路径为:0 1
节点2的最短路径长度为:25,路径为:0 1 2
节点3的最短路径长度为:12,路径为:0 4 3
节点4的最短路径长度为:15,路径为:0 4
节点5的最短路径长度为:6,路径为:0 4 5
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)