The sequential Dijkstra algorithm

Before we adapt Dijkstra's algorithm so that it works with our graph processing system, we need to have a clear idea of how the original algorithm works. The following snippet outlines an implementation of the sequential version of Dijkstra's algorithm in pseudocode form:

function Dikstra(Graph):
  for each vertex v in Graph:
      min_cost_via[v] = infinity
      prev[v] = nil
  min_cost_via[src] = 0
  
  Q = set of all vertices in graph
  while Q is not empty:
    u = entry from Q with smallest min_cost_via[]
    remove u from Q

    for each neighbor v from u:
      cost_via_u = min_cost_via[u] + cost(u, v)
      if cost_via_u < min_cost_via[v]:
        min_cost_via[v] = cost_via_u
        prev[v] = u

The preceding implementation maintains two arrays, each one having a length equal to the number of vertices in the graph:

• The first array, min_cost_via, tracks the minimum cost (distance) for reaching the source vertex from the i_th vertex in the graph.
• The prev array keeps track of the previous vertex in the optimal path leading from the source vertex to the i_th vertex.

At initialization time, we set all the entries in the prev array to nil. Additionally, all the entries in the min_cost_via array are initialized to a large number with the exception of the entry for the source vertex, whose entry is set to 0. If we were implementing this algorithm in Go and path costs were uint64 values, we would set the initial value to math.MaxUint64.

Dijkstra's algorithm is bootstrapped by placing all the graph vertices in a set called Q. The algorithm then executes a number of iterations equal to the number of vertices in the graph. At each iteration, we select vertex u from Q which has the lowest min_cost_via value and remove it from the set.

Then, the algorithm examines each neighbor v of the selected vertex u. If a lower cost path from v to the source vertex can be constructed by passing through u, then we update the min_cost_via entry for v and make u the predecessor of the optimal path to v.

The algorithm completes when all the vertices in set Q have been processed. The shortest path from the source vertex to any other vertex in the graph can be reconstructed by starting at the destination vertex and following the prev array entries until we reach the source vertex.

What's more, we can slightly tweak the preceding algorithm to obtain the original variant that answers point to point queries. All we need to do is terminate the algorithm after processing the destination vertex for our query. Those of you who are familiar with, or have implemented, the A* algorithm in the past will definitely notice a lot of similarities between the two algorithms. In fact, Dijkstra's algorithm is a special case of the A* algorithm where no distance heuristic is used.