如何用Java代码实现
时间: 2023-09-14 10:12:01 浏览: 50
以下是一个简单的Java代码实现,用于构建带权有向图、计算最短路径和查询节点信息:
```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class BusRouteGraph {
private Map<String, BusRouteNode> nodes; // 存储所有的节点
public BusRouteGraph() {
nodes = new HashMap<>();
}
// 添加节点
public void addNode(String name, List<BusRouteEdge> edges) {
BusRouteNode node = new BusRouteNode(name, edges);
nodes.put(name, node);
}
// 计算最短路径
public List<String> shortestPath(String start, String end) {
Map<String, Double> distances = new HashMap<>(); // 存储起点到每个节点的距离
Map<String, BusRouteNode> previousNodes = new HashMap<>(); // 存储每个节点的前驱节点
PriorityQueue<BusRouteNode> queue = new PriorityQueue<>(); // 存储待处理节点
// 初始化距离和前驱节点
for (String nodeName : nodes.keySet()) {
if (nodeName.equals(start)) {
distances.put(nodeName, 0.0);
} else {
distances.put(nodeName, Double.MAX_VALUE);
}
previousNodes.put(nodeName, null);
queue.offer(nodes.get(nodeName));
}
// 处理所有节点
while (!queue.isEmpty()) {
BusRouteNode node = queue.poll();
if (node.getName().equals(end)) {
break; // 已经到达终点
}
for (BusRouteEdge edge : node.getEdges()) {
double distance = distances.get(node.getName()) + edge.getWeight();
if (distance < distances.get(edge.getEnd())) {
distances.put(edge.getEnd(), distance);
previousNodes.put(edge.getEnd(), node);
queue.remove(nodes.get(edge.getEnd()));
queue.offer(nodes.get(edge.getEnd()));
}
}
}
// 构建最短路径
List<String> path = new ArrayList<>();
BusRouteNode node = nodes.get(end);
while (node != null) {
path.add(0, node.getName());
node = previousNodes.get(node.getName());
}
return path;
}
// 查询节点信息
public BusRouteNode getNode(String name) {
return nodes.get(name);
}
}
class BusRouteNode implements Comparable<BusRouteNode> {
private String name; // 节点名称
private List<BusRouteEdge> edges; // 邻居节点和边的权重
public BusRouteNode(String name, List<BusRouteEdge> edges) {
this.name = name;
this.edges = edges;
}
public String getName() {
return name;
}
public List<BusRouteEdge> getEdges() {
return edges;
}
@Override
public int compareTo(BusRouteNode other) {
return Double.compare(getDistance(), other.getDistance());
}
public double getDistance() {
// 节点到起
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)