使用java实现,给定带权有向图G=(V,E),其中每条边的权是非负实数·另外,还给定V中的一个顶 点,称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。
时间: 2024-02-16 10:04:19 浏览: 26
可以使用Dijkstra算法实现从源点到所有其他顶点的最短路径长度计算。下面是Java代码的实现:
```java
import java.util.*;
public class Dijkstra {
private static final int MAX = Integer.MAX_VALUE;
private static int[][] graph; // 带权有向图
private static int[] dist; // 存储源点到各个顶点的最短距离
private static boolean[] visited; // 标记每个顶点是否被访问过
// Dijkstra算法
private static void dijkstra(int start) {
// 初始化
Arrays.fill(dist, MAX);
Arrays.fill(visited, false);
dist[start] = 0;
// 遍历所有顶点
for (int i = 0; i < graph.length; i++) {
int u = -1;
int minDist = MAX;
// 找到当前未访问的距离源点最近的顶点
for (int j = 0; j < graph.length; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
if (u == -1) return;
visited[u] = true;
// 更新源点到未访问顶点的距离
for (int v = 0; v < graph.length; v++) {
if (!visited[v] && graph[u][v] != MAX) {
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入顶点数:");
int n = sc.nextInt();
graph = new int[n][n];
dist = new int[n];
visited = new boolean[n];
System.out.print("请输入源点编号:");
int start = sc.nextInt();
System.out.println("请输入带权有向图的邻接矩阵:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = sc.nextInt();
}
}
dijkstra(start);
System.out.println("源点到各个顶点的最短距离为:");
for (int i = 0; i < n; i++) {
System.out.print(dist[i] + " ");
}
}
}
```
在输入带权有向图的邻接矩阵后,即可输出源点到各个顶点的最短距离。