加权最短路径 java代码
时间: 2023-09-24 22:09:54 浏览: 45
以下是加权最短路径的Java代码示例:
```java
import java.util.*;
public class DijkstraAlgorithm {
private int[] distances;
private List<List<Edge>> graph;
private Set<Integer> visited;
private PriorityQueue<Edge> queue;
private int V;
private static final int MAX_DISTANCE = Integer.MAX_VALUE;
public DijkstraAlgorithm(int V) {
this.V = V;
distances = new int[V];
visited = new HashSet<>();
queue = new PriorityQueue<>(V, new EdgeComparator());
graph = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
List<Edge> edges = new ArrayList<>();
graph.add(edges);
}
}
public void addEdge(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
graph.get(source).add(edge);
}
public int[] getShortestPath(int sourceVertex) {
Arrays.fill(distances, MAX_DISTANCE);
queue.add(new Edge(sourceVertex, sourceVertex, 0));
distances[sourceVertex] = 0;
while (!queue.isEmpty()) {
Edge edge = queue.poll();
int vertex = edge.destination;
if (!visited.contains(vertex)) {
visited.add(vertex);
List<Edge> edges = graph.get(vertex);
for (Edge e : edges) {
int neighbor = e.destination;
int distance = e.weight;
if (!visited.contains(neighbor)) {
int totalDistance = distance + distances[vertex];
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
}
queue.add(new Edge(vertex, neighbor, distances[neighbor]));
}
}
}
}
return distances;
}
static class Edge {
int source;
int destination;
int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class EdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge o1, Edge o2) {
if (o1.weight < o2.weight) {
return -1;
} else if (o1.weight > o2.weight) {
return 1;
} else {
return 0;
}
}
}
}
```
以上代码实现了Dijkstra算法来查找加权有向图中的最短路径。该算法是基于贪心策略的,并使用优先队列来最优化算法的性能。