# Dijkstra's algorithm (Java)

### From LiteratePrograms

Dijkstra's algorithm is a graph algorithm that simultaneously finds the **shortest path** from a single vertex in a weighted graph to all other vertices in the graph, called the single-source shortest path problem. It works for directed and undirected graphs, but unlike the Bellman-Ford algorithm, requires nonnegative edge weights.

## Simple graph representation

We use a simple graph representation where the vertices are represented by a Vertex class.

<<Vertex class>>=classVerteximplementsComparable<Vertex>{publicfinalString name;publicEdge[]adjacencies;publicdoubleminDistance = Double.POSITIVE_INFINITY;publicVertex previous;publicVertex(String argName){name = argName;}publicString toString(){returnname;}Vertex comparator}

Because we'll need to iterate over the successors of each vertex, we will keep a list of edges exiting each vertex. For use by the algorithm later, we have two other fields:

- minDistance: The shortest distance from the source to this vertex in the graph. It is initialized to positive infinity (as large as possible).
- previous: A reference to the previous vertex to get a shortest path from the source vertex to this vertex.

In addition, later in the algorithm we will need to order the vertices. We made our class implement the `Comparable`

interface, and we will implement the actual comparison method later.

We also have a class representing an edge that stores its weight and target vertex (the vertex it points to):

<<Edge class>>=classEdge{publicfinalVertex target;publicfinaldoubleweight;publicEdge(Vertex argTarget,doubleargWeight){target = argTarget; weight = argWeight;}}

## Main algorithm

We're now prepared to define our method. We separate the computation into two stages:

- Compute the minimum distance from the source to each vertex in the graph. Simultaneously, keep track of the
`previous`

reference for each vertex*v*that gives the previous vertex on the shortest path from the source vertex to*v*. This is the expensive step. - Later, any time we want to find a particular shortest path between the source vertex and a given vertex, we follow the previous references to quickly construct it.

For the first part, we write `computePaths`

, which takes as input the source vertex from which all shortest paths are found.

<<simple compute paths function>>=publicstaticvoidcomputePaths(Vertex source){source.minDistance = 0.; visit each vertex u, always visiting vertex with smallest minDistance first // Visit each edge exiting ufor(Edge e : u.adjacencies){Vertex v = e.target;doubleweight = e.weight; relax the edge (u,v)}}}

The outline of how the function works is shown above: we visit each vertex, looping over its out-edges and adjusting `minDistance`

as necessary. The critical operation is relaxing the edges, which is based on the following formula:

- if (
*u*,*v*) is an edge and*u*is on the shortest path to*v*,*d*(*u*) +*w*(*u*,*v*) =*d*(*v*).

In other words, we can reach *v* by going from the source to *u*, then following the edge (*u*,*v*). Eventually, we will visit every predecessor of *v* reachable from the source. The shortest path goes through one of these. We keep track of the shortest distance seen so far by setting `minDistance`

and the vertex it went through by setting `previous`

:

<<relax the edge (u,v)>>=doubledistanceThroughU = u.minDistance + weight;if(distanceThroughU < v.minDistance){remove v from queue v.minDistance = distanceThroughU ; v.previous = u; re-add v to queue}

Finally, we need a way to visit the vertices in order of their minimum distance. We use Java's `PriorityQueue`

class with the minDistance as the priority. The priority queue does not like it when the ordering of its elements are changed, so when we change the minimum distance of any vertex, we need to remove it and re-insert it into the set. The queue will only consist of those vertices that have finite distance (i.e. ones we have seen); if we come to a new vertex that is not in the queue, removing it will simply do nothing.

<<Vertex comparator>>=publicintcompareTo(Vertex other){returnDouble.compare(minDistance, other.minDistance);}<<visit each vertex u, always visiting vertex with smallest minDistance first>>=PriorityQueue<Vertex> vertexQueue =newPriorityQueue<Vertex>(); vertexQueue.add(source);while(!vertexQueue.isEmpty()){Vertex u = vertexQueue.poll();<<imports>>=import java.util.PriorityQueue;

We access and remove the smallest element using `poll()`

. If we change a vertex's minimum distance, we must update its key in the map as well:

<<remove v from queue>>=vertexQueue.remove(v);<<re-add v to queue>>=vertexQueue.add(v);

This completes `computePaths()`

. `getShortestPathTo()`

is much simpler, just following the chain of `previous`

references from the target back to the source:

<<get shortest path function>>=publicstaticList<Vertex> getShortestPathTo(Vertex target){List<Vertex> path =newArrayList<Vertex>();for(Vertex vertex = target; vertex !=null; vertex = vertex.previous)path.add(vertex); Collections.reverse(path);returnpath;}<<imports>>=import java.util.List;import java.util.ArrayList;import java.util.Collections;

## Sample code

Here's some code demonstrating how we use the above functions:

<<Dijkstra.java>>=imports Vertex class Edge classpublicclassDijkstra{simple compute paths function get shortest path functionpublicstaticvoidmain(String[]args){initialize graph computePaths(v0); print out shortest paths and distances}}

Printing out shortest paths is just a matter of iterating over the vertices and calling `DijkstraGetShortestPathTo()`

on each:

<<print out shortest paths and distances>>=for(Vertex v : vertices){System.out.println("Distance to " + v + ": " + v.minDistance); List<Vertex> path = getShortestPathTo(v); System.out.println("Path: " + path);}

For this example, we choose vertices corresponding to some East Coast U.S. cities. We add edges corresponding to interstate highways, with the edge weight set to the driving distance between the cities in miles as determined by Mapquest:

<<initialize graph>>=Vertex v0 =newVertex("Harrisburg"); Vertex v1 =newVertex("Baltimore"); Vertex v2 =newVertex("Washington"); Vertex v3 =newVertex("Philadelphia"); Vertex v4 =newVertex("Binghamton"); Vertex v5 =newVertex("Allentown"); Vertex v6 =newVertex("New York"); v0.adjacencies =newEdge[]{newEdge(v1, 79.83),newEdge(v5, 81.15)}; v1.adjacencies =newEdge[]{newEdge(v0, 79.75),newEdge(v2, 39.42),newEdge(v3, 103.00)}; v2.adjacencies =newEdge[]{newEdge(v1, 38.65)}; v3.adjacencies =newEdge[]{newEdge(v1, 102.53),newEdge(v5, 61.44),newEdge(v6, 96.79)}; v4.adjacencies =newEdge[]{newEdge(v5, 133.04)}; v5.adjacencies =newEdge[]{newEdge(v0, 81.77),newEdge(v3, 62.05),newEdge(v4, 134.47),newEdge(v6, 91.63)}; v6.adjacencies =newEdge[]{newEdge(v3, 97.24),newEdge(v5, 87.94)}; Vertex[]vertices ={v0, v1, v2, v3, v4, v5, v6};

Download code |