Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section12.3Dijkstra'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)\text{.}\) However, in this section, we interpret weight as distance so that \(w(x,y)\) is now called the length of the edge \((x,y)\text{.}\) If \(P=(r=u_0,u_1,\dots,u_t=x)\) is a directed path from \(r\) to \(x\text{,}\) 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})\text{.}\) The distance from \(r\) to \(x\) is then defined to be the minimum length of a directed path from \(r\) to \(x\text{.}\) Our goal in this section is to solve the following natural problem, which has many applications:

Problem12.13

For each vertex \(x\text{,}\) find the distance from \(r\) to \(x\text{.}\) Also, find a shortest path from \(r\) to \(x\text{.}\)

Subsection12.3.1Description of the Algorithm

To describe Dijkstra's algorithm in a compact manner, it is useful to extend the definition of the function \(w\text{.}\) We do this by setting \(w(x,y)=\infty\) when \(x\neq y\) and \((x,y)\) is not a directed edge of \(\bfG\text{.}\) In this way, we will treat \(\infty\) as if it were a number (although it is not!). 1 

We are now prepared to describe Dijkstra's Algorithm.

Subsection12.3.2Example of 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\) shown in Figure 12.15. For visual clarity, we have chosen a digraph which is an oriented graph, i.e., 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)\text{.}\)

<<SVG image is unavailable, or your browser cannot render it>>

Figure12.15A digraph with edge lengths

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

Step 1. Initialization

\begin{align*} \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{align*}

Before finishing Step 1, the algorithm identifies vertex \(f\) as closest to \(a\) and appends it to \(\sigma\text{,}\) 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\text{.}\) We call this process “scanning from vertex \(f\text{.}\)” In this scan, the path to vertex \(d\) is updated, since \(\delta(f) + w(f,d)=24+120=144\lt \infty=w(a,d)\text{.}\)

Step 2. Scan from vertex \(f\)

\begin{align*} \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{align*}

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

Step 3. Scan from vertex \(c\)

\begin{align*} \sigma\amp=(a,f,c)\\ \delta(a)\amp=0; \amp P(a)\amp=(a)\\ \delta(b)\amp=102=47+55= \delta(c)+w(c,b); \amp P(b)\amp=(a,c,b)\quad\text{updated}\\ \delta(c)\amp=47; \amp P(c)\amp=(a,c)\\ \delta(d)\amp=135=47+88 = \delta(c)+w(c,d); \amp P(d)\amp=(a,c,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=113=47+66= \delta(c)+w(c,g); \amp P(g)\amp=(a,c,g)\quad\text{updated} \\ \delta(h)\amp=\infty; \amp P(h)\amp=(a,h) \end{align*}

Now vertex \(e\) is made permanent.

Step 4. Scan from vertex \(e\)

\begin{align*} \sigma\amp=(a,f,c,e)\\ \delta(a)\amp=0; \amp P(a)\amp=(a)\\ \delta(b)\amp=101=70+31= \delta(e)+w(e,b); \amp P(b)\amp=(a,e,b)\quad\text{updated}\\ \delta(c)\amp=47; \amp P(c)\amp=(a,c)\\ \delta(d)\amp=135; \amp P(d)\amp=(a,c,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=70+42= \delta(e)+w(e,g); \amp P(g)\amp=(a,e,g)\quad\text{updated}\\ \delta(h)\amp=\infty; \amp P(h)\amp=(a,h) \end{align*}

Now vertex \(b\) is made permanent.

Step 5. Scan from vertex \(b\)

\begin{align*} \sigma\amp=(a,f,c,e,b)\\ \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 = 101+ 31= \delta(b)+w(b,d); \amp P(d)\amp=(a,e,b,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=112; \amp P(g)\amp=(a,e,g)\\ \delta(h)\amp=180 = 101+79=\delta(b)+w(b,h); \amp P(h)\amp=(a,e,b,h)\quad\text{updated} \end{align*}

Now vertex \(g\) is made permanent.

Step 6. Scan from vertex \(g\)

\begin{align*} \sigma\amp=(a,f,c,e,b,g)\\ \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=178 = 112+66=\delta(g)+w(g,h); \amp P(h)\amp=(a,e,g,h)\quad\text{updated} \end{align*}

Now vertex \(d\) is made permanent.

Step 7. Scan from vertex \(d\)

\begin{align*} \sigma\amp=(a,f,c,e,b,g,d)\\ \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 = 132+29=\delta(d)+w(d,h); \amp P(h)\amp=(a,e,b,d,h)\quad\text{updated} \end{align*}

Now vertex \(h\) is made permanent. Since this is the last vertex, the algorithm halts and returns the following:

Final Results of Dijkstra's Algorithm

\begin{align*} \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{align*}

Subsection12.3.3The Correctness of Dijkstra's Algorithm

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.

Proof