最短路径的Java代码怎么写
时间: 2023-06-06 12:04:46 浏览: 47
以下是一个简单的 Java 代码实现最短路径的算法,使用 Dijkstra 算法:
```
import java.util.*;
public class ShortestPath {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); //节点个数
int m = scanner.nextInt(); //边的条数
int s = scanner.nextInt(); //起点
int t = scanner.nextInt(); //终点
// 创建邻接矩阵
int[][] graph = new int[n][n];
for (int i = 0; i < m; i++) {
int u = scanner.nextInt() - 1;
int v = scanner.nextInt() - 1;
int w = scanner.nextInt();
graph[u][v] = w;
graph[v][u] = w;
}
int[] distance = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1; // u初始化
int min = Integer.MAX_VALUE; // 用于找到未访问节点中距离最小的那个点
for (int j = 0; j < n; j++) {
if (!visited[j] && distance[j] < min) {
u = j;
min = distance[j];
}
}
if (u == -1) break; // 找不到最小距离,结束
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0) {
int newDis = distance[u] + graph[u][v];
if (newDis < distance[v]) {
distance[v] = newDis;
}
}
}
}
System.out.println(distance[t]);
}
}
```
这段代码实现了 Dijkstra 算法,用于求解从起点 `s` 到终点 `t` 的最短路径。其中,`n` 表示节点的数量,`m` 表示边的数量,`graph` 是邻接矩阵,可以表示无向带权图的边,`distance` 是每个节点到起点的距离。最后,输出的是从起点到终点的最短距离。
注意:此代码仅供参考,并不保证一定可用,具体实现还需要根据具体问题场景进行优化。