Dijkstra's Algorithm for Shortest Paths

Just as with graphs, it is useful to assign weights to the directed edges of a digraph. Specifically, in this section we consider a pair \((\bfG,w)\) where \(\GVE\) is a digraph and \(w\colon E\rightarrow\nonnegints\) is a function assigning to each directed edge \((x,y)\) a non-negative weight \(w(x,y)\). However, in this section, we interpret weight as distance so that \(w(x,y)\) is now called the length of the edge \((x,y)\). If \(P=(r=u_0,u_1,\dots,u_t=x)\) is a directed path from \(r\) to \(x\), then the length of the path \(P\) is just the sum of the lengths of the edges in the path, \(\sum_{i=0}^{t-1} w(u_iu_{i+1})\). The distance from \(r\) to \(x\) is then defined to be the minimum length of a directed path from \(r\) to \(x\). Our goal in this section is to solve the following natural problem, which has many applications:

To describe Dijkstra's algorithm in a compact manner, it is useful to extend the definition of the function \(w\). We do this by setting \(w(x,y)=\infty\) when \(x\neq y\) and \((x,y)\) is not a directed edge of \(\bfG\). In this way, we will treat \(\infty\) as if it were a number (although it is not!).This is not an issue for computer implementation of the algorithm, as instead of using \(\infty\), a value given by the product of the number of vertices and the maximum edge weight may be used to simulate infinity.

We are now prepared to describe Dijkstra's Algorithm.

Before establishing why Dijkstra's algorithm works, it may be helpful to see an example of how it works. To do this, consider the digraph \(\bfG\) For visual clarity, we have chosen a digraph which is an oriented graph, , for each distinct pair \(x,y\) of vertices, the graph contains at most one of the two possible directed edges \((x,y)\) and \((y,x)\).

Suppose that the root vertex \(r\) is the vertex labeled\(a\). The initialization step of Dijkstra's algorithm then results in the following values for \(\delta\) and \(P\):

\[\begin{aligned}\sigma\amp=(a)\amp\amp \\ \delta(a)\amp=0; \amp P(a)\amp=(a) \\ \delta(b) \amp=\infty; \amp P(b)\amp=(a,b) \\ \delta(c) \amp=47; \amp P(c)\amp=(a,c) \\ \delta(d) \amp=\infty; \amp P(d)\amp=(a,d) \\ \delta(e) \amp=70; \amp P(e)\amp=(a,e) \\ \delta(f) \amp=24; \amp P(f)\amp=(a,f) \\ \delta(g) \amp=\infty; \amp P(g)\amp=(a,g) \\ \delta(h) \amp=\infty; \amp P(h)\amp=(a,h)\end{aligned}\]

Before finishing Step 1, the algorithm identifies vertex\(f\) as closest to \(a\) and appends it to \(\sigma\), making \(a\) permanent. When entering Step 2, Dijkstra's algorithm attempts to find shorter paths from \(a\) to each of the temporary vertices by going through \(f\). We call this process scanning from vertex\(f\). In this scan, the path to vertex\(d\) is updated, since \(\delta(f) + w(f,d)=24+120=144\lt \infty=w(a,d)\).

\[\begin{aligned}\sigma\amp=(a,f)\amp\amp \\ \delta(a)\amp=0; \amp P(a)\amp=(a) \\ \delta(b)\amp=\infty; \amp P(b)\amp=(a,b) \\ \delta(c)\amp=47; \amp P(c)\amp=(a,c) \\ \delta(d)\amp=144 = 24 + 120 = \delta(f)+w(f,d); \amp P(d)\amp=(a,f,d)\quad\text{updated} \\ \delta(e)\amp=70; \amp P(e)\amp=(a,e) \\ \delta(f)\amp=24; \amp P(f)\amp=(a,f) \\ \delta(g)\amp=\infty; \amp P(g)\amp=(a,f) \\ \delta(h)\amp=\infty; \amp P(h)\amp=(a,h)\end{aligned}\]

Before proceeding to the next step, vertex\(c\) is made permanent by making it \(v_3\). In Step 3, therefore, the scan is from vertex \(c\). Vertices \(b\), \(d\), and \(g\) have their paths updated. However, although \(\delta(c) + w(c,e) = 47+23=70=\delta(e)\), we do not change \(P(e)\) since \(\delta(e)\) is not decreased by routing \(P(e)\) through \(c\).

\[\begin{aligned}\sigma\amp=(a,f,c,e,b,g,d,h) \\ \delta(a)\amp=0; \amp P(a)\amp=(a) \\ \delta(b)\amp=101; \amp P(b)\amp=(a,e,b) \\ \delta(c)\amp=47; \amp P(c)\amp=(a,c) \\ \delta(d)\amp= 132; \amp P(d)\amp=(a,e,b,d) \\ \delta(e)\amp=70; \amp P(e)\amp=(a,e) \\ \delta(f)\amp=24; \amp P(f)\amp=(a,f) \\ \delta(g)\amp=112; \amp P(g)\amp=(a,e,g) \\ \delta(h)\amp=161; \amp P(h)\amp=(a,e,b,d,h)\end{aligned}\]

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

Now that we've illustrated Dijkstra's algorithm, it's time to prove that it actually does what we claimed it does: find the distance from the root vertex to each of the other vertices and a path of that length. To do this, we first state two elementary propositions. The first is about shortest paths in general, while the second is specific to the sequence of permanent vertices produced by Dijkstra's algorithm.

We are now ready to prove the correctness of the algorithm. The proof we give will be inductive, but the induction will have nothing to do with the total number of vertices in the digraph or the step number the algorithm is in.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.