Thursday, August 21, 2014

Dijkstra Algorithm

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


Algorithm


The input for Dijkastra's algorithm is 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 steps:
  • Initialize a distance map which stores the distance of each vertex from the source. This will help in identifying next vertex with highest priority. The vertex with minimum weight will be processed next. At the beginning source will have distance as 0 and rest all vertices will be given a large number.
  • Queue stores vertices which needs to be processed yet. It provides the next vertex with minimum weight. It can be implemented using priority queue. Vertex with minimum weight will have highest priority.
  • Parent is used to map 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 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 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 it's distance and parent gets updated. 
  • Finally the method returns a MST tree list. 


Implementation


Below is Java implementation of Dijkastra's algorithm. Wikipedia has 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

No comments:

Post a Comment