用JAVA输入有向图的顶点数、边数及各条边的顶点序号对和边上的权值,建立用邻接矩阵表示的有向网。 (2)指定某个顶点,求出该顶点到其他顶点的最短路径。
时间: 2024-05-16 14:14:13 浏览: 9
以下是Java代码实现:
```java
import java.util.Arrays;
import java.util.Scanner;
public class ShortestPath {
private int vertexNum; // 顶点数目
private int edgeNum; // 边数目
private int[][] matrix; // 邻接矩阵
private boolean[] visited; // 用于记录顶点是否被访问过
private int[] dist; // 用于记录源点到各点的最短距离
private int[] path; // 用于记录源点到各点的最短路径
public ShortestPath(int vertexNum, int edgeNum) {
this.vertexNum = vertexNum;
this.edgeNum = edgeNum;
matrix = new int[vertexNum][vertexNum];
visited = new boolean[vertexNum];
dist = new int[vertexNum];
path = new int[vertexNum];
}
public void createGraph() {
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < edgeNum; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int w = scanner.nextInt();
matrix[u][v] = w;
}
scanner.close();
}
public void dijkstra(int start) {
Arrays.fill(visited, false);
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(path, -1);
dist[start] = 0;
for (int i = 0; i < vertexNum; i++) {
int u = -1;
int minDist = Integer.MAX_VALUE;
for (int j = 0; j < vertexNum; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
if (u == -1) {
return;
}
visited[u] = true;
for (int v = 0; v < vertexNum; v++) {
if (!visited[v] && matrix[u][v] != 0) {
int newDist = dist[u] + matrix[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
path[v] = u;
}
}
}
}
}
public void printShortestPath(int start) {
System.out.println("源点为:" + start);
for (int i = 0; i < vertexNum; i++) {
if (i == start) {
continue;
}
if (dist[i] == Integer.MAX_VALUE) {
System.out.println(start + "到" + i + "没有路径");
} else {
System.out.print(start + "到" + i + "的最短路径为:");
int j = i;
while (j != start) {
System.out.print(j + "<-");
j = path[j];
}
System.out.println(start);
System.out.println("最短距离为:" + dist[i]);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入顶点数目:");
int vertexNum = scanner.nextInt();
System.out.print("请输入边数目:");
int edgeNum = scanner.nextInt();
ShortestPath shortestPath = new ShortestPath(vertexNum, edgeNum);
System.out.println("请依次输入每条边的起点、终点和权值:");
shortestPath.createGraph();
System.out.print("请输入源点编号:");
int start = scanner.nextInt();
shortestPath.dijkstra(start);
shortestPath.printShortestPath(start);
scanner.close();
}
}
```
程序运行后,依次输入顶点数目、边数目、每条边的起点、终点和权值以及源点编号,即可输出从源点到各点的最短路径。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)