Intuition Behind Dijkstra's SPA

May 9, 2018

Prerequisite: Familiarity with graph data structure and recursion/dynamic programming.

Motivation

Dijkstra's Shortest Path Algorithm is one of the fundamental algorithms on graph data structures. It has many application areas thus used very frequently. There are numerous resources (textbooks, lectures etc.) from which one can learn how it works. The problem with those resources is that the following classic recipe is used to explain this algorithm:

1. List the instructions in pseudocode
2. Elaborate on the idea of each instruction

In general, this is a nice strategy to teach algorithms but in the case of Dijkstra's algorithm, it does not work well. When I was an undergrad student I learned it this way as well, but the algorithm faded in my mind in a relatively short time when I did not go over it. I think the main reason is it was not possible to state the idea of Dijkstra's algorithm in simple terms.

It turns out that there is a more intuitive and simpler explanation for this algorithm. It is unraveled when the solution to the problem is formulated recursively. The Dijkstra's algorithm essentially:

• Solves the recursive formulation through tabulation
• Includes some implementation tricks to reduce the runtime

For the better understanding of what exactly Dijkstra's SPA does, in this post, we will elaborate on the recursive formulation to solve this problem.

Idea

Problem: Given a source node \(S\), for each node \(N_i\) in the graph we would like to find a path (a sequence of nodes) from \(S\) to \(N_i\) whose cost is minimal. The cost of a path is the sum of the weights of the edges observed in the path. This problem is known as single-source shortest path problem (SSSP). Let us only consider the graphs with non-negative edge weights.

To show the recursive relation, as always, we assume that we already have the solution to a smaller version of the problem. In this case:

• Let \(K\) denote the set of nodes in which we know the shortest paths to and the costs associated with them.
  • Includes \(S\) too.
  • None of the paths follow a node that is not in \(K\).
• Let \(T\) be the set of nodes that have an immediate connection to \(K\).
  • In other words, the nodes that have an edge to at least one of the nodes in \(K\).
• Furthermore, let \(L\) be the set of nodes that are not in \(K\) or \(T\).

Key Observation:

Among the paths that go from \(S\) to the nodes in the immediate neighbourhood of set \(K\) using only the nodes in \(K\), the one with the smallest cost is the shortest path from \(S\) to the node where the path ends.

Procedure and Optimization

This recursive relation is easiest implemented by tabulation. Starting from the base case we grow the set \(K\) one node at a time. The following is the inefficient pseudocode describing the procedure.

Input:  N, number of nodes
	E, set of edges with weights
	s, source node
Output: cost, shortest path cost to each node

procedure dijkstraSSSP
  // base case
  cost[s] = 0
  K = {s}

  // tabulate N-1 times
  for i = 2 ... N
    T = getImmediateNodes(K)    
    shortestNode = -1
    shortestCost = Inf
    for each node in T
      for each (source,node,weight) in E
        if cost[source] + weight < shortestCost
          shortestCost = cost[source] + weight
          shortestNode = node
        end
      end
    end

    cost[shortestNode] = shortestCost
    K.add(shortestNode)
  end
end

Optimization Idea: Essentially we have a set of costs (of paths that go to nodes in \(T\) from \(S\)) in which sometimes we add and remove elements (caused by moving node from set \(T\) to \(K\)). We are interested in the minimum element in this set. This is the perfect scenario for heaps.

Remarks

Once one notices the above-mentioned guarantee, the idea is very simple to implement. What makes the regular explanation of Dijkstra's algorithm hard is:

• No explanation for the guarantee/observation
• Optimized code with implementation details