public class dt { private int[][] graph;//声明一个整型数组 public dt(int numStations) { graph = new int[numStations][numStations]; for (int i = 0; i < numStations; i++) { Arrays.fill(graph[i], Integer.MAX_VALUE); graph[i][i] = 0; } } public void addConnection(int station1, int station2, int cost) {//权值(最短路径长度) graph[station1][station2] = cost;//去程 graph[station2][station1] = cost;//返程 } public int getShortestPath(int startStation, int endStation) { int numStations = graph.length; // 使用Floyd算法计算所有对的最短路径 for (int k = 0; k < numStations; k++) { for (int i = 0; i < numStations; i++) { for (int j = 0; j < numStations; j++) { if (graph[i][k] != Integer.MAX_VALUE && graph[k][j] != Integer.MAX_VALUE) { graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]); } } } } return graph[startStation][endStation]; } public static void main(String[] args) { dt subway = new dt(6); subway.addConnection(0, 1, 3); subway.addConnection(0, 2, 2); subway.addConnection(1, 3, 4); subway.addConnection(2, 5, 5); subway.addConnection(2, 4, 6); subway.addConnection(3, 4, 1); subway.addConnection(3, 5, 5); subway.addConnection(4, 5, 2); Scanner sc = new Scanner(System.in); System.out.println("输入上车站点"); int num1 =sc.nextInt(); System.out.println("输入下车站点"); int num2 =sc.nextInt(); int shortestPath = subway.getShortestPath(num1, num2); System.out.println("车站"+num1+"到"+"车站"+num2+"需要" + shortestPath+"元"); } } 增加打印路径代码
时间: 2024-03-26 18:39:20 浏览: 21
要打印出最短路径,可以在 `getShortestPath` 方法中记录下最短路径信息,然后在方法结束时打印出来。可以将一个 `int` 类型的二维数组 `path` 用于记录路径信息,其中 `path[i][j]` 表示从站点 `i` 到站点 `j` 的最短路径的上一个站点,如果 `i` 到 `j` 之间没有路径,则 `path[i][j]` 为 `-1`。在计算最短路径时,如果发现通过中转站 `k` 能够获得更短的路径,则更新 `path[i][j]` 为 `k`。最后,我们可以通过递归的方式输出从起点到终点的路径。
下面是增加打印路径代码后的 `dt` 类的完整代码:
```java
import java.util.Arrays;
import java.util.Scanner;
public class dt {
private int[][] graph;
private int[][] path;
public dt(int numStations) {
graph = new int[numStations][numStations];
path = new int[numStations][numStations];
for (int i = 0; i < numStations; i++) {
Arrays.fill(graph[i], Integer.MAX_VALUE);
Arrays.fill(path[i], -1);
graph[i][i] = 0;
}
}
public void addConnection(int station1, int station2, int cost) {
graph[station1][station2] = cost;
graph[station2][station1] = cost;
path[station1][station2] = station2;
path[station2][station1] = station1;
}
public int getShortestPath(int startStation, int endStation) {
int numStations = graph.length;
for (int k = 0; k < numStations; k++) {
for (int i = 0; i < numStations; i++) {
for (int j = 0; j < numStations; j++) {
if (graph[i][k] != Integer.MAX_VALUE && graph[k][j] != Integer.MAX_VALUE) {
if (graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
path[i][j] = path[i][k];
}
}
}
}
}
printPath(startStation, endStation);
return graph[startStation][endStation];
}
private void printPath(int startStation, int endStation) {
System.out.print("从车站" + startStation + "到车站" + endStation + "的路径为:");
printPathHelper(startStation, endStation);
System.out.println();
}
private void printPathHelper(int startStation, int endStation) {
if (startStation == endStation) {
System.out.print(startStation);
} else if (path[startStation][endStation] == -1) {
System.out.print("无法到达");
} else {
int nextStation = path[startStation][endStation];
printPathHelper(startStation, nextStation);
System.out.print(" -> " + endStation);
}
}
public static void main(String[] args) {
dt subway = new dt(6);
subway.addConnection(0, 1, 3);
subway.addConnection(0, 2, 2);
subway.addConnection(1, 3, 4);
subway.addConnection(2, 5, 5);
subway.addConnection(2, 4, 6);
subway.addConnection(3, 4, 1);
subway.addConnection(3, 5, 5);
subway.addConnection(4, 5, 2);
Scanner sc = new Scanner(System.in);
System.out.println("输入上车站点");
int num1 = sc.nextInt();
System.out.println("输入下车站点");
int num2 = sc.nextInt();
int shortestPath = subway.getShortestPath(num1, num2);
System.out.println("从车站" + num1 + "到" + "车站" + num2 + "需要" + shortestPath + "元");
}
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)