Dijkstra.java

packagecom.jwetherell.algorithms.graph;

importjava.util.ArrayList;
importjava.util.Collection;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
importjava.util.PriorityQueue;
importjava.util.Queue;

importcom.jwetherell.algorithms.data_structures.Graph;

/**
 * Dijkstra's shortest path. Only works on non-negative path weights. Returns a
 * tuple of total cost of shortest path and the path.
 * <p>
 * Worst case: O(|E| + |V| log |V|)
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra's Algorithm (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassDijkstra {

privateDijkstra() { }

publicstaticMap<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> getShortestPaths(Graph<Integer> graph, Graph.Vertex<Integer> start) {
finalMap<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>> paths = newHashMap<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>>();
finalMap<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>> costs = newHashMap<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>>();

getShortestPath(graph, start, null, paths, costs);

finalMap<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> map = newHashMap<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>>();
for (Graph.CostVertexPair<Integer> pair : costs.values()) {
intcost = pair.getCost();
Graph.Vertex<Integer> vertex = pair.getVertex();
List<Graph.Edge<Integer>> path = paths.get(vertex);
map.put(vertex, newGraph.CostPathPair<Integer>(cost, path));
 }
returnmap;
 }

publicstaticGraph.CostPathPair<Integer> getShortestPath(Graph<Integer> graph, Graph.Vertex<Integer> start, Graph.Vertex<Integer> end) {
if (graph == null)
throw (newNullPointerException("Graph must be non-NULL."));

// Dijkstra's algorithm only works on positive cost graphs
finalbooleanhasNegativeEdge = checkForNegativeEdges(graph.getVertices());
if (hasNegativeEdge)
throw (newIllegalArgumentException("Negative cost Edges are not allowed."));

finalMap<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>> paths = newHashMap<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>>();
finalMap<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>> costs = newHashMap<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>>();
returngetShortestPath(graph, start, end, paths, costs);
 }

privatestaticGraph.CostPathPair<Integer> getShortestPath(Graph<Integer> graph, 
Graph.Vertex<Integer> start, Graph.Vertex<Integer> end,
Map<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>> paths,
Map<Graph.Vertex<Integer>, Graph.CostVertexPair<Integer>> costs) {
if (graph == null)
throw (newNullPointerException("Graph must be non-NULL."));
if (start == null)
throw (newNullPointerException("start must be non-NULL."));

// Dijkstra's algorithm only works on positive cost graphs
booleanhasNegativeEdge = checkForNegativeEdges(graph.getVertices());
if (hasNegativeEdge)
throw (newIllegalArgumentException("Negative cost Edges are not allowed."));

for (Graph.Vertex<Integer> v : graph.getVertices())
paths.put(v, newArrayList<Graph.Edge<Integer>>());

for (Graph.Vertex<Integer> v : graph.getVertices()) {
if (v.equals(start))
costs.put(v, newGraph.CostVertexPair<Integer>(0, v));
else
costs.put(v, newGraph.CostVertexPair<Integer>(Integer.MAX_VALUE, v));
 }

finalQueue<Graph.CostVertexPair<Integer>> unvisited = newPriorityQueue<Graph.CostVertexPair<Integer>>();
unvisited.add(costs.get(start));

while (!unvisited.isEmpty()) {
finalGraph.CostVertexPair<Integer> pair = unvisited.remove();
finalGraph.Vertex<Integer> vertex = pair.getVertex();

// Compute costs from current vertex to all reachable vertices which haven't been visited
for (Graph.Edge<Integer> e : vertex.getEdges()) {
finalGraph.CostVertexPair<Integer> toPair = costs.get(e.getToVertex()); // O(1)
finalGraph.CostVertexPair<Integer> lowestCostToThisVertex = costs.get(vertex); // O(1)
finalintcost = lowestCostToThisVertex.getCost() + e.getCost();
if (toPair.getCost() == Integer.MAX_VALUE) {
// Haven't seen this vertex yet

// Need to remove the pair and re-insert, so the priority queue keeps it's invariants
unvisited.remove(toPair); // O(n)
toPair.setCost(cost);
unvisited.add(toPair); // O(log n)

// Update the paths
List<Graph.Edge<Integer>> set = paths.get(e.getToVertex()); // O(log n)
set.addAll(paths.get(e.getFromVertex())); // O(log n)
set.add(e);
 } elseif (cost < toPair.getCost()) {
// Found a shorter path to a reachable vertex

// Need to remove the pair and re-insert, so the priority queue keeps it's invariants
unvisited.remove(toPair); // O(n)
toPair.setCost(cost);
unvisited.add(toPair); // O(log n)

// Update the paths
List<Graph.Edge<Integer>> set = paths.get(e.getToVertex()); // O(log n)
set.clear();
set.addAll(paths.get(e.getFromVertex())); // O(log n)
set.add(e);
 }
 }

// Termination conditions
if (end != null && vertex.equals(end)) {
// We are looking for shortest path to a specific vertex, we found it.
break;
 }
 }

if (end != null) {
finalGraph.CostVertexPair<Integer> pair = costs.get(end);
finalList<Graph.Edge<Integer>> set = paths.get(end);
return (newGraph.CostPathPair<Integer>(pair.getCost(), set));
 }
returnnull;
 }

privatestaticbooleancheckForNegativeEdges(Collection<Graph.Vertex<Integer>> vertitices) {
for (Graph.Vertex<Integer> v : vertitices) {
for (Graph.Edge<Integer> e : v.getEdges()) {
if (e.getCost() < 0)
returntrue;
 }
 }
returnfalse;
 }
}