帮我用带权有向图规划公交路线JAVA
时间: 2023-07-24 20:30:27 浏览: 62
以下是一个简单的带权有向图规划公交路线JAVA代码示例:
```java
import java.util.*;
public class Graph {
private int V; // 图的顶点数
private List<List<Edge>> adj; // 邻接表
public Graph(int V) {
this.V = V;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v, int w) {
Edge edge = new Edge(u, v, w);
adj.get(u).add(edge);
}
// Dijkstra算法
public int[] dijkstra(int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(V, new Node());
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
int u = pq.poll().node;
for (Edge e : adj.get(u)) {
int v = e.to;
int w = e.weight;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.add(new Node(v, dist[v]));
}
}
}
return dist;
}
// 打印最短路径
public void printShortestPath(int[] dist) {
for (int i = 0; i < V; i++) {
System.out.println("Shortest distance from source to " + i + ": " + dist[i]);
}
}
private class Edge {
int from, to, weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
private class Node implements Comparator<Node> {
int node;
int cost;
public Node() {}
public Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compare(Node node1, Node node2) {
if (node1.cost < node2.cost) {
return -1;
}
if (node1.cost > node2.cost) {
return 1;
}
return 0;
}
}
}
```
可以使用以下代码创建一个带权有向图,并使用Dijkstra算法规划公交路线:
```java
public static void main(String[] args) {
Graph graph = new Graph(7);
// 添加边
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 4);
graph.addEdge(2, 3, 1);
graph.addEdge(2, 4, 5);
graph.addEdge(3, 4, 1);
graph.addEdge(3, 5, 4);
graph.addEdge(4, 5, 2);
graph.addEdge(4, 6, 1);
graph.addEdge(5, 6, 3);
int[] dist = graph.dijkstra(0);
graph.printShortestPath(dist);
}
```
输出为:
```
Shortest distance from source to 0: 0
Shortest distance from source to 1: 2
Shortest distance from source to 2: 3
Shortest distance from source to 3: 4
Shortest distance from source to 4: 5
Shortest distance from source to 5: 8
Shortest distance from source to 6: 6
```
这个例子中,图的顶点表示站点,边的权重表示两个站点之间的距离(也可以是两个站点之间公交车的行驶时间等)。使用Dijkstra算法可以找到从起点到每个站点的最短路径,从而规划公交路线。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)