Last modified: April 22nd, 1997

The shortest-paths problem involves a weighted, possibly directed graph described by the set of edges and vertices {E,V}. (For an introduction to the terminology used in graph descriptions, please see Topic #25.) Given a source vertex, s, the goal is to find the shortest existing path between s and any of the other vertices in the graph. Each path, therefore, will have the minimum possible sum of its component edges' (u,v) weights (w[u,v]). The method described here is Dijkstra's algorithm.

Nota bene: Formally, what one tends to think of as the "length" of an edge is known as its "weight." Thus, a graph whose edges are all of equal "length" is unweighted, whereas a graph with edges of differing "lengths" is weighted. The term "weight" is used because graphs are not limited to representing locations on a plane or in space; consequently edges could represent time, cost, and so on, generally a quantity which is to be kept minimal when going from any vertex to another. As this document deals with 'shortest paths' however, we will often use the term "length" for the sake of clarity.

Shortest-path algorithms are a topic closely related to breadth-first searches (BFS). In fact, the BFS algorithm is used to determine the shortest path between two points in an unweighted graph. It can be easily adapted to search a weighted graph whose edges' weights are all integers (or, by extension, all multiples of a common factor).

All that is required is to replace each edge of weight w (where w > 1) with a chain of w-1 "ghost" nodes. Thus, when the algorithm runs, it will correctly report the shortest path, as it 'perceives' the distance between nodes A and B as twice as long than that between B and C (see illustration).

When it is not convenient to employ the "ghost node" strategy, however, it is necessary to use Dijkstra's algorithm.

Edsger W. Dijkstra is a Dutch computer scientist and mathematician who has made a number of remarkable contributions to computer science. Among the many algorithms he originated, the shortest path algorithm explained here is probably the best known. He is also known for his outspoken views on everything concerning computer science, including some rather damning words about certain programming languages.

The basic reasoning behind the algorithm is as follows:

Here is the formal notation of the algorithm:

      1.  for each u  G:
    1.1.      d[u]  infinity;
    1.2.      p[u]  NIL;
      2.  d[s]  0;
      3.  S  Ø;
      4.  Q  V;
      5.  while NotEmpty(Q):
    5.1.      u  DeleteTop(Q);
    5.2.      S  S union { u };
    5.3.          for each v adjacent to u:
  5.3.1.              if d[v] > d[v] + w[u, v]:
5.3.1.1.                  d[v] = d[u] + w[u, v];
5.3.1.2.                  p[v] = u;
5.3.2.3.                  DecreaseKey[v, Q];

And here's an example of the algorithm in action: (The red edges are the ones which are put into the search tree).

Dijkstra's algorithm is an example of what are known as greedy algorithms. This means that it follows a general philosophy of finding a locally optimal solution -- considering only a small part of the available data -- in this case, adding the closest vertex to the solution set -- with the assumption that repeating this process will allow the solution to "grow" into one that is globally optimal. Although this is not in fact the result for all greedy algorithms, it is true in the case of Dijkstra's.

Here we use the technique of proof by contradiction. That is to say, we start out making an assumption which is faulty and, by making logical deductions, arrive at a conclusion which contradicts our original assumption, which we thereby prove to be false.

We can prove that by the time we get around to assimilating any given vertex, the path leading up to that vertex will be the shortest one as long as all the preceding vertices were assimilated using their shortest path. Therefore, this is also proof by induction. For our base case we can simply use the assimilation of the source, which of course has its distance field set to zero.

Here is a 'snapshot' of the algorithm. At this point, u has made it to the top of the priority queue. Now the question is: Where is the shortest path to the source? Either it is indicated by p[u], which takes it directly into the solution set and thence, via p1, to the source, or there exists some other unknown path which does not follow p[u] and then go directly to the source (two possibilities, p2 and p3, are indicated in red). In order to prove that p[u] does in fact indicate the shortest path, we begin by assuming the opposite: that the shortest path to u from inside the solution set (the "island") is some other path (p2, p3, etc.), which may even weave in and out of S, possibly several times -- basically, it could be anything. Any such path implies the existence of some vertex x, outside the solution set and on the supposedly shortest path to the source -- for example, x1 and x2 on the illustration.

Here is our contradiction: Given that x is before u on u's shortest path, it must be that d[x] is less than d[u]. However, since u has reached the top of the priority queue before x, it must be that d[x] is in fact greater than d[u]. As this is obviously impossible, our original assumption, that p[u] is not the beginning of u's shortest path to the source, must be false.

Finally, now that we've proven that d[u] is correct for every u we insert into the solution set, we only need to prove that we correctly deal with updating the d[] field of vertices outside the solution set for each iteration of the loop. We will dispense with a formal proof, however, and only state that the relaxation algorithm correctly takes care of this issue.

QED!

We cannot analyze the complexity of Dijkstra's algorithm without having picked an ADT for the priority queue, since we do not know what the complexity of the individual operations (MakeNull, DeleteTop and DecreaseKey). However, we can determine the number of times each operations is executed, and decide later what the total will be.

Our options are summarized in the following table. We can either use a simple, unsorted table (surprisingly, this is a realistic choice for certain kinds of graphs), a standard heap, or a rather remarkable data structure called a Fibonacci heap. This is a rather complex implementation, and we won't go into its features here.

	Unsorted table	"Standard" heap	Fibonacci heap
MakeNull	(1) Total: (1)	(1) Total: (1)	(1) Total: (1)
DeleteTop	(|V|) Total: (|V|)	(log|V|) Total: (|V|log|V|)	(log|V|) Total: (|V|log|V|)
DecreaseKey	(1) Total: (|E|)	(log|V|) Total: (|E|log|V|)	(1) Total: (|E|)
Overall complexity	(|V| + |E|) = (|V|)	((|V|+|E|)log|V|)	(|V|log|V|+|E|)

This applet simulates the use of the Dijkstra algorithm. The instructions are pretty much self-explanatory. Here, take a look at the source.

This material is based on course notes and the compulsory text, Introduction to Algorithms by Cormen, Leiserson and Rivest (MIT Press/McGraw-Hill 1994, ISBN 0-262-03141-8 (MIT Press) and ISBN 0-07-013143-0 (McGraw-Hill).

The HTML was written using SLED and Windows NotePad and tested using Netscape 2.02 and Netscape 3.01. (Like you care, but anyways.)

Graphics were created using Visio and Deluxe Paint II Enhanced. They were converted to GIF format using xv and CompuShow 2000.

Java was written using Microsoft's J++ package.

This document is on the following persons' conscience:

Please feel free to hassle us about anything you see fit. :^>