-
Notifications
You must be signed in to change notification settings - Fork 3
/
DijkstraShortestPath.java
107 lines (88 loc) · 2.88 KB
/
DijkstraShortestPath.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package Graphs;
import DataStructure.IndexMinPriorityQueue;
import DataStructure.Stack;
import java.util.Arrays;
import java.util.TreeMap;
public class DijkstraShortestPath {
private double[] distTo;
private int[] edgeTo;
private IndexMinPriorityQueue<Double> indexMinPQ;
private static final double INFINITY = Double.POSITIVE_INFINITY;
/**
* Uses Dijkstra's Algorithm to find the shortest
* path from a source to every reachable vertex
* in a edge weighted directed graph.
* <p/>
* If the graph contains edges with a negative weight,
* an IllegalArgumentException is thrown.
*
* @param graph
* @param source
*/
public DijkstraShortestPath(EdgeWeightedDirectedGraph graph, int source) {
checkNegativeEdges(graph);
distTo = new double[graph.vertices()];
edgeTo = new int[graph.vertices()];
Arrays.fill(distTo, INFINITY);
distTo[source] = 0;
indexMinPQ = new IndexMinPriorityQueue<Double>(graph.vertices());
indexMinPQ.insert(source, 0.);
while (!indexMinPQ.isEmpty()) {
int vertex = indexMinPQ.deleteMin();
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 (indexMinPQ.contains(to)) indexMinPQ.decreaseKey(to, distTo[to]);
else indexMinPQ.insert(to, distTo[to]);
}
}
private void checkNegativeEdges(EdgeWeightedDirectedGraph graph) {
for (DirectedEdge edge : graph.edgesIterator()) {
if (edge.weight() < 0) throw new IllegalArgumentException("Negative edges!");
}
}
/**
* Returns true if there is a path from the source
* to the vertex. Otherwise, returns false.
*
* @param vertex
*/
public boolean hasPathTo(int vertex) {
return distTo[vertex] < INFINITY;
}
/**
* Returns the distance from the source to
* the given vertex. If the vertex is
* unreachable, the distance returned is
* Double.POSITIVE_INFINITY.
*
* @param vertex
*/
public double distTo(int vertex) {
return distTo[vertex];
}
/**
* Returns the edges from the source to the given vertex,
* is such a path exists. Otherwise, it returns null.
*
* @param vertex
*/
public Iterable<Integer> pathTo(int vertex) {
if (!hasPathTo(vertex)) return null;
Stack<Integer> edges = new Stack<Integer>();
int node;
for (node = vertex; distTo[node] != 0; node = edgeTo[node]) {
edges.push(node);
}
edges.push(node);
return edges;
}
}