Dijkstra

This page provides introduction to Dijkstra Algorithm.

Overview

Dijkstra's is single source shortest path algorithm. It works on both direct and undirected graph but doesn't work if graph has negative weight.

Let's apply dijkstra's algorithm on below undirected graph.

Suppose we want to calculate the distance from node $\text{A}$. Initially, we set the distance from $\text{A}$ to all other nodes to the maximum possible value, except for itself, and store these distances in a hashmap. We also initialize a priority queue to store the distance of each specific node from $\text{A}$.

We poll the element with the shortest distance from the priority queue($\text{A}$) and visit all its neighbor($\text{B, D, F}$). If the current distance of a neighbor node from $\text{A}$ in the hashmap is greater than the sum of the current node's distance from $\text{A}$ and the distance to that neighbor, we update the distance in the hashmap.

For example, the current distance of node $\text{B}$ in hashmap is $\infty$. We override it's distance in distance hashmap to $5$ which is sum of $0$ (distance of current node $\text{A}$ from $\text{A}$) and $5$ (distance between current node $\text{A}$ and it's neighbor $\text{B}$). Similarly, for we override the distance for $\text{D, F}$.

info

Nodes marked in gray represent polled nodes, while those marked in green are newly added nodes. A node is added to the priority queue only if a shorter distance to reach that node is found compared to the one currently stored in the distance hashmap.

Poll node $\text{F}$ which has shortest distance in priority queue and visit all it's neighbors.

info

Notice we did not add node $\text{A}$ back into in the priority queue, as it's new distance through current path is greater than existing distance, which was found through another path.

Poll node $\text{B}$ which has shortest distance in priority queue and visit all it's neighbors.

Poll node $\text{E}$ which has shortest distance in priority queue and visit all it's neighbors.

info

Notice how we readded node $\text{D}$ to priority queue when we found better path to reach $\text{D}$ and also updated distance hashmap, as show in above image. Removing existing distance of node $\text{D}$ from priority queue is an option but it takes $\text{O(N)}$ time complexity.

Poll node $\text{C}$ which has shortest distance in priority queue and visit all it's neighbors.

Poll node $\text{D}$ which has shortest distance in priority queue and visit all it's neighbors.

Poll node $\text{D}$ which has shortest distance in priority queue and visit all it's neighbors.

Priority Queue has no more element, you have shortest distance of node $\text{A}$ from all the other nodes in the graph.

Java

class Edge {
  char ch;
  int distance;
  Edge(char ch, int distance) {
    this.ch = ch;
    this.distance = distance
  }

  @Override 
  public int compareTo(Edge other) {
    // ascending order by distance
    return Integer.compare(this.distance, other.distance);
  }
}

public HashMap<Character, Integer> dijkstra(HashMap<Character, List<Edge>> graph) {
  HashMap<Character, Integer> distance = new HashMap<>();
  PriorityQueue<Edge> pq = new PriorityQueue<>();

  for(Character ch: graph.keySet()) distance.put(ch, Integer.MAX_VALUE);
  distance.put('A', 0);
  pq.offer(new Edge('A', 0));

  while(!pq.isEmpty()) {
    // poll the node with shortest distance
    Edge e = pq.poll();

    // visit all children of current node 
    for(Edge child: graph.getOrDefault(e.ch, new ArrayList<>())) {
      int oldDistance = distance.get(child.ch);
      int newDistance = distance.get(e.ch) + child.distance;
      if(newDistance < oldDistance) {
        pq.offer(new Edge(child.ch, newDistance));
        distance.put(child.ch, newDistance);
      }
    }
  }
}

Complexity

Let's say there are $\text{V}$ vertices and $\text{E}$ edges in a graph.

Time Complexity

Priority queue takes $\text{O(log V)}$ time for both poll and add operation, given that there are $\text{V}$ elements in the priority queue at any given time. We need to perform priority queue operations at most $\text{E}$ times as there are total $\text{E}$ edges.

The total time complexity will be as below:

$$\text{O(E log V)}$$

Space Complexity

The algorithm uses space to store the distances of all vertices in a hashmap and stores the vertices in a priority queue as it iterates through the edges.

The total space complexity will be as below:

$$\text{O(V)}$$