在此基础上用java代码实现这个区域的重要场所至少有10个。若有人咨询,只需提供起始点和目的地,咨询结果是一条公交线路提供重要区域的信息查询功能,包括场所名称、经过的公交线路等信息。要求使用图相关知识实现。用键盘输出。
时间: 2024-03-12 12:49:34 浏览: 16
以下是针对区域有10个重要场所的代码实现:
```
import java.util.*;
class Graph {
// 定义顶点和边的信息
private Map<String, List<Edge>> graph;
public Graph() {
graph = new HashMap<>();
// 添加重要场所的信息
graph.put("学校", Arrays.asList(new Edge("图书馆", 5), new Edge("超市", 10)));
graph.put("图书馆", Arrays.asList(new Edge("学校", 5), new Edge("公园", 8)));
graph.put("超市", Arrays.asList(new Edge("学校", 10), new Edge("银行", 15)));
graph.put("公园", Arrays.asList(new Edge("图书馆", 8), new Edge("医院", 12)));
graph.put("银行", Arrays.asList(new Edge("超市", 15), new Edge("餐厅", 20)));
graph.put("医院", Arrays.asList(new Edge("公园", 12), new Edge("商场", 25)));
graph.put("餐厅", Arrays.asList(new Edge("银行", 20), new Edge("电影院", 30)));
graph.put("商场", Arrays.asList(new Edge("医院", 25), new Edge("体育馆", 40)));
graph.put("电影院", Arrays.asList(new Edge("餐厅", 30), new Edge("游泳馆", 45)));
graph.put("体育馆", Arrays.asList(new Edge("商场", 40), new Edge("游泳馆", 35)));
graph.put("游泳馆", Arrays.asList(new Edge("电影院", 45), new Edge("体育馆", 35)));
}
public List<Edge> getEdges(String vertex) {
return graph.get(vertex);
}
}
class Edge {
// 定义边的信息
private String to;
private int weight;
public Edge(String to, int weight) {
this.to = to;
this.weight = weight;
}
public String getTo() {
return to;
}
public int getWeight() {
return weight;
}
}
class ShortestPath {
// 最短路径算法
public static Map<String, Integer> dijkstra(Graph graph, String source) {
Map<String, Integer> dist = new HashMap<>();
Set<String> visited = new HashSet<>();
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
pq.add(new Edge(source, 0));
while (!pq.isEmpty()) {
Edge curr = pq.poll();
String currVertex = curr.getTo();
int currDist = curr.getWeight();
if (visited.contains(currVertex)) {
continue;
}
visited.add(currVertex);
dist.put(currVertex, currDist);
for (Edge e : graph.getEdges(currVertex)) {
if (!visited.contains(e.getTo())) {
pq.add(new Edge(e.getTo(), currDist + e.getWeight()));
}
}
}
return dist;
}
}
class Query {
// 查询函数
public static void query(Graph graph, String start, String end) {
Map<String, Integer> dist = ShortestPath.dijkstra(graph, start);
if (!dist.containsKey(end)) {
System.out.println("无法到达目的地!");
return;
}
System.out.println("从 " + start + " 到 " + end + " 的最短路径为:");
System.out.println(start);
int totalDist = dist.get(end);
String currVertex = end;
while (!currVertex.equals(start)) {
for (Edge e : graph.getEdges(currVertex)) {
if (dist.containsKey(e.getTo()) && dist.get(e.getTo()) + e.getWeight() == dist.get(currVertex)) {
System.out.println(e.getTo() + "(乘坐公交" + e.getWeight() + "分钟)");
currVertex = e.getTo();
break;
}
}
}
System.out.println("到达 " + end + " 需要 " + totalDist + " 分钟。");
}
}
public class TrafficGuideSystem {
public static void main(String[] args) {
// 读入区域的公交线路,将其表示成一个带权有向图
Graph graph = new Graph();
// 循环提供咨询服务,直到用户输入exit
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("请输入起点和终点(用空格分隔),输入exit退出:");
String input = scanner.nextLine();
if (input.equals("exit")) {
break;
}
String[] parts = input.split(" ");
String start = parts[0];
String end = parts[1];
// 输出最短路径的信息
Query.query(graph, start, end);
}
}
}
```
这个代码实现中,我们将重要场所的信息存储在一个哈希表中,图的每个顶点对应一个链表,链表中存储了该顶点到其他顶点的边的信息。查询函数使用最短路径算法求出起点到终点的最短路径,并输出经过的场所和乘坐公交的时间。
相关推荐
![](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)