#### Java: Dijkstra algorithm

Dijkstra algorithm

/************************************************************************** * File: Dijkstra.java * Author: Keith Schwarz () * * An implementation of Dijkstra's single-source shortest path algorithm. * The algorithm takes as input a directed graph with non-negative edge * costs and a source node, then computes the shortest path from that node * to each other node in the graph. * * The algorithm works by maintaining a priority queue of nodes whose * priorities are the lengths of some path from the source node to the * node in question. At each step, the algortihm dequeues a node from * this priority queue, records that node as being at the indicated * distance from the source, and then updates the priorities of all nodes * in the graph by considering all outgoing edges from the recently- * dequeued node to those nodes. * * In the course of this algorithm, the code makes up to |E| calls to * decrease-key on the heap (since in the worst case every edge from every * node will yield a shorter path to some node than before) and |V| calls * to dequeue-min (since each node is removed from the prioritiy queue * at most once). Using a Fibonacci heap, this gives a very good runtime * guarantee of O(|E| + |V| lg |V|). * * This implementation relies on the existence of a FibonacciHeap class, also * from the Archive of Interesting Code. You can find it online at * * http://keithschwarz.com/interesting/code/?dir=fibonacci-heap */ import java.util.*; // For HashMap public final class Dijkstra { /** * Given a directed, weighted graph G and a source node s, produces the * distances from s to each other node in the graph. If any nodes in * the graph are unreachable from s, they will be reported at distance * +infinity. * * @param graph The graph upon which to run Dijkstra's algorithm. * @param source The source node in the graph. * @return A map from nodes in the graph to their distances from the source. */ public staticMap shortestPaths(DirectedGraph graph, T source) { /* Create a Fibonacci heap storing the distances of unvisited nodes * from the source node. */ FibonacciHeap pq = new FibonacciHeap (); /* The Fibonacci heap uses an internal representation that hands back * Entry objects for every stored element. This map associates each * node in the graph with its corresponding Entry. */ Map > entries = new HashMap >(); /* Maintain a map from nodes to their distances. Whenever we expand a * node for the first time, we'll put it in here. */ Map result = new HashMap (); /* Add each node to the Fibonacci heap at distance +infinity since * initially all nodes are unreachable. */ for (T node: graph) entries.put(node, pq.enqueue(node, Double.POSITIVE_INFINITY)); /* Update the source so that it's at distance 0.0 from itself; after * all, we can get there with a path of length zero! */ pq.decreaseKey(entries.get(source), 0.0); /* Keep processing the queue until no nodes remain. */ while (!pq.isEmpty()) { /* Grab the current node. The algorithm guarantees that we now * have the shortest distance to it. */ FibonacciHeap.Entry curr = pq.dequeueMin(); /* Store this in the result table. */ result.put(curr.getValue(), curr.getPriority()); /* Update the priorities of all of its edges. */ for (Map.Entry arc : graph.edgesFrom(curr.getValue()).entrySet()) { /* If we already know the shortest path from the source to * this node, don't add the edge. */ if (result.containsKey(arc.getKey())) continue; /* Compute the cost of the path from the source to this node, * which is the cost of this node plus the cost of this edge. */ double pathCost = curr.getPriority() + arc.getValue(); /* If the length of the best-known path from the source to * this node is longer than this potential path cost, update * the cost of the shortest path. */ FibonacciHeap.Entry dest = entries.get(arc.getKey()); if (pathCost < dest.getPriority()) pq.decreaseKey(dest, pathCost); } } /* Finally, report the distances we've found. */ return result; } }

**Tag:** Java, Algorithm, Dijkstra

## 0 Comments