再给我一个用户输入的示例
时间: 2024-02-02 11:03:57 浏览: 60
当然可以,下面是一个用户输入邻接表的示例代码:
```
import java.util.ArrayList;
import java.util.List;
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();
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
System.out.println("请输入邻接表:");
for (int i = 0; i < n; i++) {
System.out.print("请输入节点" + i + "的邻接节点个数:");
int cnt = sc.nextInt();
System.out.println("请输入节点" + i + "的邻接节点及其边权:");
for (int j = 0; j < cnt; j++) {
int v = sc.nextInt();
int w = sc.nextInt();
graph.get(i).add(new Edge(v, w));
}
}
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(List<List<Edge>> graph, int n, int s, int[] dist) {
boolean[] visited = new boolean[n];
visited[s] = true;
for (int i = 0; i < n; i++) {
dist[i] = Integer.MAX_VALUE;
}
dist[s] = 0;
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 (Edge e : graph.get(minIndex)) {
int v = e.v;
int w = e.w;
if (!visited[v] && dist[minIndex] != Integer.MAX_VALUE && dist[minIndex] + w < dist[v]) {
dist[v] = dist[minIndex] + w;
}
}
}
}
static class Edge {
int v;
int w;
public Edge(int v, int w) {
this.v = v;
this.w = w;
}
}
}
```
在上述代码中,使用了一个List<List<Edge>>类型的邻接表来存储图的信息。首先读取节点数n和源节点编号s,然后创建邻接表graph。对于每个节点i,先读取该节点的邻接节点个数cnt,然后读取cnt个邻接节点及其边权,并将其添加到邻接表中。在调用dijkstra函数计算最短路径时,将这些变量作为参数传递给dijkstra函数。最后输出源节点到各个节点的最短距离。
阅读全文