编写java代码,有向图,节点为node 边为edge ,并求该图形的两点之间最短路径及长度。如果不可达则写成-1
时间: 2023-03-19 18:22:26 浏览: 99
下面是使用Java语言实现有向图最短路径算法的示例代码。该算法基于Dijkstra算法实现。
```java
import java.util.*;
public class ShortestPath {
private final int V; // 节点数
private List<Edge>[] adj; // 邻接表
private static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public ShortestPath(int V) {
this.V = V;
adj = new List[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int from, int to, int weight) {
adj[from].add(new Edge(to, weight));
}
public int[] dijkstra(int s) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(s, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.u;
int d = node.dist;
if (d != dist[u]) {
continue;
}
for (Edge e : adj[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new Node(v, dist[v]));
}
}
}
return dist;
}
private static class Node implements Comparable<Node> {
int u;
int dist;
Node(int u, int dist) {
this.u = u;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
return Integer.compare(dist, o.dist);
}
}
public static void main(String[] args) {
ShortestPath graph = new ShortestPath(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 4, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 0, 7);
graph.addEdge(3, 2, 6);
graph.addEdge(4, 1, 3);
graph.addEdge(4, 2, 9);
graph.addEdge(4, 3, 2);
int[] dist = graph.dijkstra(0);
System.out.println("Shortest path from 0 to 3: " + dist[3]);
System.out.println("Shortest path from 0 to 4: " + dist[4]);
System.out.println("Shortest path from 2 to 0: " + dist[2]);
}
}
```
在上述代码中,`ShortestPath`类表示有向图,节点数为`V`。`addEdge`方法用于向图中添加一条从节点`from`到节点`to`,权重为`weight`的有向边。`dijkstra`方法计算从起点`s`到所有其他节点的最短路径,并返回一个包含所有最短路径的数组。其中,`Node`类表示一个节点及其到起点的距离,用于
阅读全文