Dijkstra's algorithm (Java)

From LiteratePrograms

Other implementations: C++ | Inform 7 | Java | Scala

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>>=
class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    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>>=
class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}

Main algorithm

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

1. 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.
2. 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>>=
public static void computePaths(Vertex source)
{
    source.minDistance = 0.;
    visit each vertex u, always visiting vertex with smallest minDistance first
        // Visit each edge exiting u
        for (Edge e : u.adjacencies)
        {
            Vertex v = e.target;
            double weight = 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)>>=
double distanceThroughU = 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>>=
public int compareTo(Vertex other)
{
    return Double.compare(minDistance, other.minDistance);
}
<<visit each vertex u, always visiting vertex with smallest minDistance first>>=
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<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>>=
public static List<Vertex> getShortestPathTo(Vertex target)
{
    List<Vertex> path = new ArrayList<Vertex>();
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        path.add(vertex);
    Collections.reverse(path);
    return path;
}
<<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 class
public class Dijkstra
{
    simple compute paths function
    get shortest path function
    public static void main(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 = new Vertex("Harrisburg");
Vertex v1 = new Vertex("Baltimore");
Vertex v2 = new Vertex("Washington");
Vertex v3 = new Vertex("Philadelphia");
Vertex v4 = new Vertex("Binghamton");
Vertex v5 = new Vertex("Allentown");
Vertex v6 = new Vertex("New York");
v0.adjacencies = new Edge[]{ new Edge(v1,  79.83),
                             new Edge(v5,  81.15) };
v1.adjacencies = new Edge[]{ new Edge(v0,  79.75),
                             new Edge(v2,  39.42),
                             new Edge(v3, 103.00) };
v2.adjacencies = new Edge[]{ new Edge(v1,  38.65) };
v3.adjacencies = new Edge[]{ new Edge(v1, 102.53),
                             new Edge(v5,  61.44),
                             new Edge(v6,  96.79) };
v4.adjacencies = new Edge[]{ new Edge(v5, 133.04) };
v5.adjacencies = new Edge[]{ new Edge(v0,  81.77),
                             new Edge(v3,  62.05),
                             new Edge(v4, 134.47),
                             new Edge(v6,  91.63) };
v6.adjacencies = new Edge[]{ new Edge(v3,  97.24),
                             new Edge(v5,  87.94) };
Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };

Download code