Dijkstra's Algorithm

The Dijkstra's Algorithm (shortest route) finds the shortest distance and path from a source to all destination in a directed graph which is defined by a set of vertexes (V) and a collection of edges.

I found the easiest way to understand how Dijkstra's algorithm works is to take a look at this visual explanation below: 

The Approach

Initially, set the distance from the source to each destination node to a very high value.  These nodes with a very high initial value are not in settled nor in unsettled set.

Dijkstra partitions nodes into two distinct sets - unsettled (unsolved) and settled. Nodes in unsettled set are those nodes still must be evaluated for a shortest path from the source. Nodes in settled set are those nodes that have their shortest distance from the sources found already. There are some nodes with a very high initial value are not in the settled set nor in the unsettled set to begin with. Nodes are gradually added to the unsettled set first before being moved in the settled set.

To find the shortest distance, Dijkstra's algorithm selects a node from unsettled set, recalculate the distance from source to all its adjacent nodes (neighbors), then put the selected node to the settled set, and newly found adjacent nodes to the unsettled set. The selections is based on the least distance from the source to the unsettled node. This selection process is the findMinimalDistances(node) as seen below in the sample code. The selection process goes on until there's no node left in the unsettled set.

Thought Process

Before we start, initialize the distance from the source to each destination node to a very high value.

First, put only the source node into the unsettled set.

Then, go through iterations. In each iteration, select the node with the lowest distance from the source from the unsettled set, put it into the settled set. Repeat until the unsettled set is empty.

In each iteration, the algorithm selects one node with the lowest distance from the source out from the unsettled set. It also reads all edges which are outgoing from the selected node and evaluates each destination node in these edges and add these adjacent nodes to the unsettled set. Check if the known distance from the source to this destination node can be reduced if the selected edge is used. If this can be done, then the shortest distance (from the source to each destination) is updated and the node is added to the nodes which need evaluation.

Code Snippets

Model

A simple Vertex class with its hashCode() and equals() overridden. Remember, if a class overrides equals(), most likely, you must override hashCode() as well.

public class Vertex{
  private final String id;
  
  public Vertex(String id) {
    this.id = id;
  }
  public String getId() {
    return id;
  }

  public int hashCode() {
    int result = 5;
    result = 31 * result + ((id == null) ? 0 : id.hashCode());
    return result;
  }
  
  public boolean equals(Object obj) {
    if (this == obj)
      return true;
    if (obj == null)
      return false;
    if (getClass() != obj.getClass())
      return false;
    Vertex other = (Vertex) obj;
    if (id == null) {
      if (other.id != null)
        return false;
    } else if (!id.equals(other.id))
      return false;
    return true;
  }

  public String toString() {
    return id;
  }
} 

A simple Edge class contains source vertex, destination vertex, uni-directional weight, with some getter, and setter functions:

public class Edge{
  private final String id; 
  private final Vertex source;
  private final Vertex destination;
  private final int weight; 
  
  public Edge(String id, Vertex source, Vertex destination, int weight) {
    this.id = id;
    this.source = source;
    this.destination = destination;
    this.weight = weight;
  }
  
  public String getId() {
    return id;
  }
  public Vertex getDestination() {
    return destination;
  }

  public Vertex getSource() {
    return source;
  }
  public int getWeight() {
    return weight;
  }
  
  public String toString() {
    return source + " " + destination;
  }
} 

Graph = {Vertex, Edge}:

public class Graph{
  private final List<Vertex> vertexes;
  private final List<Edge> edges;

  public Graph(List<Vertex> vertexes, List<Edge> edges) {
    this.vertexes = vertexes;
    this.edges = edges;
  }

  public List<Vertex> getVertexes() {
    return vertexes;
  }

  public List<Edge> getEdges() {
    return edges;
  } 
}

Dijkstra's Algorithm Implementation

Dijkstra's algorithm deals with a graph, so we choose to have the constructor to take in a Graph. Internally, the Dijkstra's algorithm class contains nodes and edges of the graph, plus the intermediate data structures (settled nodes, unsettled nodes, predecessors, and distance) to support the algorithm. Among them, the 'predecessors' Map is to trace the predecessor of a given node for the shortest path from the source, and the 'distance' Map is to hold the min distance going from the source node to any given vertex.

public class DijkstraAlgorithm {

  private final List<Vertex> nodes;
  private final List<Edge> edges;
  private Set<Vertex> settledNodes;
  private Set<Vertex> unSettledNodes;
  private Map<Vertex, Vertex> predecessors; // predecessor of V1 is V2
  private Map<Vertex, Integer> distance; // distance from source to a vertex

  public DijkstraAlgorithm(Graph graph) {
    // create a copy of the array so that we can operate on this array
    this.nodes = new ArrayList<Vertex>(graph.getVertexes());
    this.edges = new ArrayList<Edge>(graph.getEdges());
  }

At its core, execute(Vertex) is the main function that actually perform the Dijkstra's algorithm. At the end, the 'distance' Map will have the shortest distance from the given source vertex to all other vertex.

  public void execute(Vertex source) {
    settledNodes = new HashSet<Vertex>();
    unSettledNodes = new HashSet<Vertex>();
    distance = new HashMap<Vertex, Integer>();    // 1
    predecessors = new HashMap<Vertex, Vertex>(); // 2
    distance.put(source, 0);
    unSettledNodes.add(source);
    while (unSettledNodes.size() > 0) {
      Vertex node = getMinimum(unSettledNodes);   // 3
      settledNodes.add(node);                     // add to settled set
      unSettledNodes.remove(node);                // remove from unsettled set
      findMinimalDistances(node);  // 4
    }
  }

[1] In Dijkstra's algorithm, this Map holds temporary distance from source vertex to any other given vertex.
[2] This Map holds temporary predecessor of a given Vertex. A predecessor is a Vertex in a shortest path found so far before reaching a given Vertex. To look up a predecessor of a vertex V, just do predecessors.get(V).
[3] Return a vertex among all unsettled nodes with the least distance from the source.
[4] Given a node, go through its adjacent nodes. Recalculate the shortest distance held in 'distance' Map where temporary distance from source is held. Then add all adjacent node into unsettled set.

The rest are helper functions called and used from execute(Vertex): 

  // Given a node, go through its adjacent nodes. Recalculate the shortest
  // distance held in 'distance' Map where temporary distance from source is
  // held. Then add all adjacent nodes into the unsettled set. 
  private void findMinimalDistances(Vertex node) {
    List<Vertex> adjacentNodes = getNeighbors(node);
    for (Vertex target : adjacentNodes) {
      if (getShortestDistance(target) > getShortestDistance(node)
          + getDistance(node, target)) {
        distance.put(target, getShortestDistance(node)
            + getDistance(node, target));
        predecessors.put(target, node); // put() replaces existing key
        unSettledNodes.add(target);     // add to unsettled set
      }
    }

  }

  // return the directional distance from node to target vertex
  private int getDistance(Vertex node, Vertex target) {
    for (Edge edge : edges) {
      if (edge.getSource().equals(node)
          && edge.getDestination().equals(target)) {
        return edge.getWeight();
      }
    }
    throw new RuntimeException("Should not happen");
  }

  private List<Vertex> getNeighbors(Vertex node) {
    List<Vertex> neighbors = new ArrayList<Vertex>();
    for (Edge edge : edges) {
      if (edge.getSource().equals(node)
          && !isSettled(edge.getDestination())) {
        neighbors.add(edge.getDestination());
      }
    }
    return neighbors;
  }

  // Given vertexes, return the vertex with the least distance from the source
  private Vertex getMinimum(Set<Vertex> vertexes) {
    Vertex minimum = null;
    for (Vertex vertex : vertexes) {
      if (minimum == null) {
        minimum = vertex;
      } else {
        if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
          minimum = vertex;
        }
      }
    }
    return minimum;
  }

  private boolean isSettled(Vertex vertex) {
    return settledNodes.contains(vertex);
  }

  // Return the distance from the source; MAX_VALUE if no applicable.
  private int getShortestDistance(Vertex destination) {
    Integer d = distance.get(destination);
    if (d == null) {
      return Integer.MAX_VALUE;
    } else {
      return d;
    }
  }

  /*
   * This method returns the path from the source to the selected target and
   * NULL if no path exists
   */
  public LinkedList<Vertex> getPath(Vertex target) {
    LinkedList<Vertex> path = new LinkedList<Vertex>();
    Vertex step = target;
    // check if a path exists
    if (predecessors.get(step) == null) {
      return null;
    }
    path.add(step);
    while (predecessors.get(step) != null) {
      step = predecessors.get(step);
      path.add(step);
    }
    // Put it into the correct order
    Collections.reverse(path);
    return path;
  }

}  

references

• Java equals() and hashCode() Contract
  
• Overridding equals() and hashCode() in Java