单源最短路径贪心算法java 需要用户输入
时间: 2023-08-04 12:25:33 浏览: 63
用贪心算法解单源最短路径问题.doc
当然可以,您可以在程序中添加用户输入模块来读取用户输入的源节点和邻接矩阵。下面的示例代码可以实现用户输入功能:
```
import java.util.Scanner;
public class Dijkstra {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入节点数:");
int n = sc.nextInt();
System.out.print("请输入源节点编号:");
int s = sc.nextInt();
int[][] graph = new int[n][n];
System.out.println("请输入邻接矩阵:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = sc.nextInt();
}
}
sc.close();
int[] dist = new int[n];
dijkstra(graph, n, s, dist);
System.out.println("源节点到各个节点的最短距离为:");
for (int i = 0; i < n; i++) {
System.out.println(s + " -> " + i + ": " + dist[i]);
}
}
public static void dijkstra(int[][] graph, int n, int s, int[] dist) {
boolean[] visited = new boolean[n];
visited[s] = true;
for (int i = 0; i < n; i++) {
dist[i] = graph[s][i];
}
for (int i = 0; i < n - 1; i++) {
int minDist = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
minIndex = j;
}
}
if (minIndex == -1) {
break;
}
visited[minIndex] = true;
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[minIndex][j] != Integer.MAX_VALUE) {
dist[j] = Math.min(dist[j], dist[minIndex] + graph[minIndex][j]);
}
}
}
}
}
```
在上述代码中,通过Scanner类实现用户输入功能。首先读取节点数n和源节点编号s,然后读取邻接矩阵graph。在调用dijkstra函数计算最短路径时,将这些变量作为参数传递给dijkstra函数。最后输出源节点到各个节点的最短距离。
阅读全文