用java代码实现针对有若干重要场所的某一区域设计一个交通指南系统,指导前来咨询者以最低的票价(或者最少的时间)从区域中的某一个场所到达另一个场所。要求: 用一个带权有向图表示某一个区域的公交线路。 这个区域的重要场所至少有10个。 若有人咨询,只需提供起始点和目的地,咨询结果是一条公交线路
时间: 2024-03-07 20:46:41 浏览: 20
好的,以下是Java代码实现:
```java
import java.util.*;
public class TransportationGuideSystem {
private int[][] graph;
private int[][] dist;
private int[][] cost;
private int n;
// 构造函数,初始化带权有向图
public TransportationGuideSystem(int[][] g, int[][] c, int num) {
n = num;
graph = new int[n][n];
cost = new int[n][n];
dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = g[i][j];
cost[i][j] = c[i][j];
if (i != j && graph[i][j] == 0) {
graph[i][j] = Integer.MAX_VALUE / 2;
} // 若两个节点之间没有边,则权值设为无穷大
dist[i][j] = graph[i][j];
}
}
}
// Dijkstra算法,计算最短路径
public int dijkstra(int s, int t) {
boolean[] vis = new boolean[n];
int[] d = new int[n];
int[] p = new int[n];
Arrays.fill(vis, false);
Arrays.fill(d, Integer.MAX_VALUE / 2);
Arrays.fill(p, -1);
d[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!vis[j] && (u == -1 || d[u] > d[j])) {
u = j;
}
}
vis[u] = true;
for (int v = 0; v < n; v++) {
if (!vis[v] && dist[u][v] != Integer.MAX_VALUE / 2) {
if (d[v] > d[u] + dist[u][v]) {
d[v] = d[u] + dist[u][v];
p[v] = u;
}
}
}
}
int pos = t;
int count = 0;
while (pos != s) {
count++;
pos = p[pos];
}
return count;
}
// Floyd算法,计算最短路径
public int floyd(int s, int t) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int pos = t;
int count = 0;
while (pos != s) {
count++;
for (int i = 0; i < n; i++) {
if (dist[s][i] + cost[i][pos] == dist[s][pos]) {
pos = i;
break;
}
}
}
return count;
}
public static void main(String[] args) {
int n = 10;
int[][] graph = new int[n][n];
int[][] cost = new int[n][n];
// 初始化带权有向图中的边权值
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
graph[i][j] = graph[j][i] = (int) ((Math.random() * 10) + 1);
cost[i][j] = cost[j][i] = (int) ((Math.random() * 10) + 1);
}
}
TransportationGuideSystem ts = new TransportationGuideSystem(graph, cost, n);
int start = (int) (Math.random() * n);
int end = (int) (Math.random() * n);
System.out.println("起始点:" + start + ",目的地:" + end);
System.out.println("最少票价需要乘坐" + ts.dijkstra(start, end) + "辆公交车。");
System.out.println("最短时间需要乘坐" + ts.floyd(start, end) + "辆公交车。");
}
}
```
以上代码实现了一个交通指南系统,通过随机生成的带权有向图,计算出从起始点到目的地最少需要乘坐的公交车数量,分别使用Dijkstra算法和Floyd算法计算最短路径。用户只需提供起始点和目的地即可得到咨询结果。