使用java实现带权有向图的针对有若干重要场所的某一区域设计一个交通指南系统,指导前来咨询者以最低的票价(或者最少的时间)从区域中的某一个场所到达另一个场所
时间: 2024-03-07 16:50:18 浏览: 17
好的,我可以为您提供一个基于 Java 的带权有向图实现的示例代码,供您参考。
```
import java.util.*;
// 表示图中的一个节点
class Node {
public String name; // 节点名称
public List<Edge> edges; // 与该节点相关的边
public Node(String name) {
this.name = name;
this.edges = new ArrayList<>();
}
// 添加一条边到该节点
public void addEdge(Edge e) {
this.edges.add(e);
}
}
// 表示图中的一条边
class Edge {
public Node from; // 边的起点
public Node to; // 边的终点
public int weight; // 边的权值
public Edge(Node from, Node to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
// 带权有向图
class WeightedDirectedGraph {
public List<Node> nodes; // 所有的节点
public WeightedDirectedGraph() {
this.nodes = new ArrayList<>();
}
// 添加一个节点到图中
public void addNode(Node node) {
this.nodes.add(node);
}
// 添加一条边到图中
public void addEdge(Node from, Node to, int weight) {
Edge e = new Edge(from, to, weight);
from.addEdge(e);
}
}
// 使用 Dijkstra 算法计算从起点到终点的最短路径
class Dijkstra {
public static List<Node> shortestPath(WeightedDirectedGraph graph, Node start, Node end) {
// 初始化距离表和前驱表
Map<Node, Integer> distance = new HashMap<>(); // 距离表,记录起点到每个节点的距离
Map<Node, Node> predecessor = new HashMap<>(); // 前驱表,记录最短路径中每个节点的前驱节点
for (Node node : graph.nodes) {
distance.put(node, Integer.MAX_VALUE);
predecessor.put(node, null);
}
distance.put(start, 0);
// 创建一个优先队列,按节点距离从小到大排序
Queue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(distance::get));
queue.offer(start);
// 开始计算最短路径
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (curr == end) {
break; // 已经找到终点,退出循环
}
// 遍历当前节点的所有出边
for (Edge edge : curr.edges) {
Node next = edge.to;
int newDistance = distance.get(curr) + edge.weight;
if (newDistance < distance.get(next)) {
// 更新距离表和前驱表
distance.put(next, newDistance);
predecessor.put(next, curr);
queue.offer(next);
}
}
}
// 构造最短路径
List<Node> path = new ArrayList<>();
Node node = end;
while (node != null) {
path.add(0, node);
node = predecessor.get(node);
}
return path;
}
}
// 示例代码
public class Main {
public static void main(String[] args) {
// 创建一个带权有向图
WeightedDirectedGraph graph = new WeightedDirectedGraph();
Node n1 = new Node("A");
Node n2 = new Node("B");
Node n3 = new Node("C");
Node n4 = new Node("D");
Node n5 = new Node("E");
graph.addNode(n1);
graph.addNode(n2);
graph.addNode(n3);
graph.addNode(n4);
graph.addNode(n5);
graph.addEdge(n1, n2, 2);
graph.addEdge(n1, n3, 5);
graph.addEdge(n2, n3, 1);
graph.addEdge(n2, n4, 3);
graph.addEdge(n3, n4, 1);
graph.addEdge(n3, n5, 2);
graph.addEdge(n4, n5, 4);
// 计算从起点 A 到终点 E 的最短路径
List<Node> path = Dijkstra.shortestPath(graph, n1, n5);
// 输出最短路径
for (Node node : path) {
System.out.print(node.name + " ");
}
// 输出:A B C D E
}
}
```
这段示例代码实现了一个带权有向图,并使用 Dijkstra 算法计算从起点到终点的最短路径。您可以根据自己的需求和数据结构来进行修改和扩展。