-
Notifications
You must be signed in to change notification settings - Fork 3
/
BellmanFordShortestPath.java
66 lines (45 loc) · 1.65 KB
/
BellmanFordShortestPath.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package Graphs;
import DataStructure.IndexMinPriorityQueue;
import DataStructure.Queue;
import java.util.Arrays;
public class BellmanFordShortestPath {
private double[] distTo;
private int[] edgeTo;
private boolean[] onQueue;
private Queue<Integer> verticesToCheck;
private IndexMinPriorityQueue<Double> indexMinPQ;
public BellmanFordShortestPath(EdgeWeightedDirectedGraph graph, int source) {
distTo = new double[graph.vertices()];
Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[source] = 0.0;
edgeTo = new int[graph.vertices()];
onQueue = new boolean[graph.vertices()];
indexMinPQ = new IndexMinPriorityQueue<Double>(graph.vertices());
verticesToCheck = new Queue<Integer>();
verticesToCheck.enqueue(source);
while (!verticesToCheck.isEmpty()) {
int v = verticesToCheck.dequeue();
onQueue[v] = false;
relax(graph, v);
}
}
private void relax(EdgeWeightedDirectedGraph graph, int vertex) {
for (DirectedEdge edge : graph.adjEdges(vertex)) {
relax(edge);
}
}
private void relax(DirectedEdge edge) {
int from = edge.from();
int to = edge.to();
if (distTo[to] > edge.weight() + distTo[from]) {
distTo[to] = edge.weight() + distTo[from];
edgeTo[to] = from;
if (!onQueue[to]) {
onQueue[to] = true;
verticesToCheck.enqueue(to);
}
if (indexMinPQ.contains(to)) indexMinPQ.decreaseKey(to, distTo[to]);
else indexMinPQ.insert(to, distTo[to]);
}
}
}