Dijkstra Algorithm

Dijkstra's algorithm finds the shortest distance from vertex s to t in a Graph.  In fact, it finds the shortest path from the source, s, to all other vertices/nodes of the graph. Due to this, it is also referred to as a single-source shortest path. It's a greedy algorithm and does NOT work on graphs with negative weight/cost edges.

Algorithm

The input for Dijkstra's algorithm is a graph object and the source or initial vertex. Shortest distance to all other vertices from this initial vertex will get computed after the completion of the algorithm. Below are the steps:

• Initialize a distance map which stores the distance of each vertex from the source. This will help in identifying the next vertex with the highest priority. The vertex with minimum weight will be processed next. In the beginning, the source will have distance as 0 and rest all vertices will be given a large number.
• Queue stores vertices which need to be processed yet. It provides the next vertex with minimum weight. It can be implemented using the priority queue. Vertex with minimum weight will have the highest priority.
• Parent is used to mapping each node to its parent. This will be helpful to find the path from source to a given destination vertex/node.
• Visited set stores already visited vertices. This helps in considering only unvisited neighbors for expanding algorithm. 
• Each cycle of the while loop calculates the shortest distance to one node from the initial source node. 
• From a given vertex, u, it identifies unvisited adjacent vertices. And then for all adjacent vertices weights are relaxed.
• Relaxation process(i.e. relax method) updates the cost of all the vertices, v, connected to vertex, u. It checks if the current estimated cost of v can be improved by going through u. 
• After each while loop, one vertex with minimum weight is removed from the queue and its distance and parent gets updated. 
• Finally, the method returns an MST tree list. 

Implementation

Below is Java implementation of Dijkstra's algorithm. Wikipedia has a beautiful animation showing the progress of the algorithm.

package graph.algo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * Single Source Shortest Path Dijkstra Algorithm
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class Dijkstra<V> {
 private Map<V, Integer> distance;
 private Map<V, V> parent;
 private Graph<V> graph;
 private Set<V> queue;

 public Dijkstra(Graph<V> graph) {
  // distance of each vertex from source
  this.distance = new LinkedHashMap<V, Integer>();

  // stores parent of each vertex
  this.parent = new LinkedHashMap<>();

  // input graph
  this.graph = graph;

  // used as input for providing next vertex
  // with minimum weight
  this.queue = new HashSet<V>();
 }

 /**
  * Initialize supporting data structure
  * 
  * @param source
  */
 private void initialize(V source) {
  Iterator<V> itr = graph.getAllVertices().iterator();
  while (itr.hasNext()) {
   distance.put(itr.next(), Integer.MAX_VALUE);
  }
  distance.put(source, 0);

  queue.addAll(distance.keySet());
 }

 /**
  * Dijkstra algorithm Takes input source vertex to start
  * 
  * @param source
  */
 public List<V> getShortestPath(V source) {
  Objects.requireNonNull(source);
  if (this.graph == null || this.graph.isEmpty()) {
   throw new IllegalStateException(
     "Valid graph object is required !!!");
  }

  List<V> traversedOrder = new ArrayList<>();

  this.initialize(source);
  Set<V> visited = new HashSet<>(); // set of vertices whose path have
           // already been found

  int wtuv = 0;

  while (!queue.isEmpty()) {

   // extract vertex with minimum weight
   V u = this.extractMinFromQueue();
   visited.add(u);

   traversedOrder.add(u);

   List<V> neighbors = this.graph.getAdjacentVertices(u);
   neighbors.removeAll(visited); // consider only unvisited nodes

   if (!neighbors.isEmpty()) {
    for (V v : neighbors) {
     wtuv = this.graph.getWeight(u, v);
     relax(u, v, wtuv);
    }
   }
  }
  return traversedOrder;
 }

 /**
  * Updates distance of node v from source node u
  * 
  * @param u
  *            source vertex
  * @param v
  *            target vertex
  * @param wtuv
  */
 private void relax(V u, V v, long wtuv) {
  if (distance.get(v) > distance.get(u) + wtuv) {
   distance.put(v, distance.get(u) + (int) wtuv);
   parent.put(v, u);
   // System.out.println(" u,v --"+ u + " , "+ v + " distance --> "+
   // distance);
  }
 }

 /**
  * Extract next vertex with smallest weight /highest priority removes the
  * node (optional) Can be implemented through priority queue
  * 
  * @return V vertex
  */
 private V extractMinFromQueue() {
  int weight = Integer.MAX_VALUE;
  V minVertex = null;
  for (V v : this.queue) {
   if (distance.get(v) < weight) {
    minVertex = v;
    weight = distance.get(v);
   }
  }
  if (minVertex != null)
   this.queue.remove(minVertex);
  return minVertex;
 }

 /**
  * Test method
  * 
  * @param args
  */
 public static void main(String[] args) {
  Graph<Integer> graph = new Graph<Integer>();

  graph.addEdge(1, 2, 5);
  graph.addEdge(2, 1, 5);

  graph.addEdge(1, 3, 12);
  graph.addEdge(3, 1, 12);

  graph.addEdge(2, 3, 6);
  graph.addEdge(3, 2, 6);

  graph.addEdge(2, 4, 13);
  graph.addEdge(4, 2, 13);

  graph.addEdge(3, 4, 5);
  graph.addEdge(4, 3, 5);

  Dijkstra<Integer> d = new Dijkstra<>(graph);

  System.out.println(graph.toString());
  List<Integer> path = d.getShortestPath(1);
  System.out.println(" Path or traversed vertices --" + path);
  System.out.println(" Distance Map for each vertex --" + d.distance);
  System.out.println(" Vertex and it's parent vertex Map --" + d.parent);

 }

}

Output:
Set of Edges :
1 -- (5)--->2
1 -- (12)--->3
2 -- (5)--->1
2 -- (6)--->3
2 -- (13)--->4
3 -- (12)--->1
3 -- (6)--->2
3 -- (5)--->4
4 -- (13)--->2
4 -- (5)--->3
& Set of vertices :[1, 2, 3, 4]
 Path or traversed vertices --[1, 2, 3, 4]
 Distance Map for each vertex --{1=0, 2=5, 3=11, 4=16}
 Vertex and it's parent vertex Map --{2=1, 3=2, 4=3}

Important Points

1. Time complexity of algorithm is O(n^2); where n is number of vertices.
2. All pair shortest path can be calculated by calling Dijkastra algorithm from each of the n possible vertices. 
3. It works correctly only on graphs without negative-cost edges. 
4. This algorithm generates shortest path tree with source as tree root. 
5. If you want to find the shortest distance only to a target vertex/node; break loop once the target node is processed. 

References

https://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html