城市最短路径问题有权值广度优先算法java实现
时间: 2023-07-26 09:12:36 浏览: 53
是的,有权值广度优先算法可以用来解决城市最短路径问题,下面是 Java 实现的代码:
```java
import java.util.*;
public class CityShortestPath {
// 表示边的类
static class Edge {
int from;
int to;
int weight;
Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
// 广度优先搜索求最短路径
static int shortestPath(int n, int[][] graph, int start, int end) {
// 构建图的邻接表
List<List<Edge>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : graph) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
adj.get(from).add(new Edge(from, to, weight));
adj.get(to).add(new Edge(to, from, weight)); // 无向图需要添加反向边
}
// 广度优先搜索
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离为无穷大
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
dist[start] = 0;
while (!queue.isEmpty()) {
int curr = queue.poll();
for (Edge e : adj.get(curr)) {
int next = e.to;
int weight = e.weight;
if (dist[next] > dist[curr] + weight) {
dist[next] = dist[curr] + weight;
queue.offer(next);
}
}
}
return dist[end];
}
public static void main(String[] args) {
int n = 5;
int[][] graph = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 5}, {2, 3, 1}, {2, 4, 3}, {3, 4, 2}};
int start = 0;
int end = 4;
int shortest = shortestPath(n, graph, start, end);
System.out.println("The shortest path from " + start + " to " + end + " is " + shortest);
}
}
```
这里假设 `graph` 是一个二维数组,每行表示一条边,第一列是起点,第二列是终点,第三列是边权值。`n` 是图中节点的个数,`start` 和 `end` 分别是起点和终点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)