3 - Dijkstra's single source shortest path algorithm

This is an algorithm every computer course student will remember until the Alzheimer or the alcohol had killed enough brain cells. If not by its application, then by its author's name that is really cool :)

Single source shortest path algorithms are very useful to everyone without doubt, because can be used to determine the best route from a starting point to other points in a graph. Imagine then this graph like the streets in your city. Now you can know the best path from your house to the supermarket.

There are variations of the problem (more than one path, more then one starting point, etc) and therefore several solutions,  but I've chosen Dijkstra's algorithm because it is a classic solution for a classic problem (ok, first because my good friend Lourenço asked me) : finding the best possible path between a source and a destination, once given several possible paths.

Before showing the algorithm some conditions must be stated:

1. the algorithm assume that the problem is represented as a graph;


2. the graph must be a directed graph (no cycles allowed);


3. the graph's edges must be weighted always with positive values;

Considering this, given a graph G=(V,E), all vertexes in V must be initialized as  infinite because in the first state we don't know the minimum distance from the source to any given destination. The exception it the origin who must be tagged as zero (the distance between the origin and itself).

The algorithm will then loop through all vertexes picking the one with the minimum shortest path (in the first iteration the origin will be selected), until all the vertexes in V are selected. When selected, the vertex is stored in a set S, which on the end will hold the vertexes that compose the shortest path. The selection of each vertex is usually implemented as a min-priority queue that will dictate the algorithm's performance.

For each selected vertex, its successors must be tagged with the costs for going from the source until that specific successor. This cost is nothing more that the sum of the edge weight with the value previously attributed to the selected vertex, and the tagging is done only if the new cost is less than a previous attributed cost.

Mr. Cormen [1] refers to this processes as relaxation, and I took the liberty of reproducing bellow (hopefully I won't be sued) the pseudo-code for Dijkstra's that appears in Introduction to Algorithms (second edition).

DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  S ← Ø
3  Q ← V[G]
4  while Q ≠ Ø
5      do u ← EXTRACT-MIN(Q)
6         S ← S ∪{u}
7         for each vertex v ∈ Adj[u]
8             do RELAX(u, v, w)

RELAX(u, v, w)
1  if d[v] > d[u] + w(u, v)
2     then d[v] ← d[u] + w(u, v)
3          π[v] ← u

INITIALIZE-SINGLE-SOURCE(G, s)
1  for each vertex v ∈ V[G]
2       do d[v] ← ∞
3          π[v] ← NIL
4  d[s] 0

This page has some very illustrative Java applets that show the algorithm in action.

The algorithm has a wide usage when determining distance costs - I would not be surprised if Google were using it in Google Maps :) - but it can also be used to solve another problems that can be specified as nodes and weighted transitions. One example would be finding the best possible move in a chess match, where each possible move would be a vertex and the cost of each move (from the chess-master point of view) would be an edge weight.

There are also some works on solving the Rubik's cube problem using Dijkstra's single source shortest path algorithm, like this one here.

References:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (McGraw-Hill Science / Engineering / Math, 2003), second edn.