maths.free › Combinatorics & Graph Theory › 12. Graph Algorithms › Dijkstra's Algorithm for Shortest Paths

Dijkstra's Algorithm for Shortest Paths

Just as with graphs, it is useful to assign weights to the directed edges of a digraph.

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:

Problem

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

Description of the Algorithm

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.

Algorithm: Dijkstra's Algorithm

Let \(n=|V|\). At Step\(i\), where \(1\le i\le n\), we will have determined:

A sequence \(\sigma=(v_1,v_2,v_3,\dots,v_i)\) of distinct vertices from \(\bfG\) with \(r=v_1\). These vertices are called permanent vertices, while the remaining vertices will be called temporary vertices.
For each vertex \(x\in V\), we will have determined a number \(\delta(x)\) and a path \(P(x)\) from \(r\) to \(x\) of length \(\delta(x)\).

Initialization (Step1)
Set \(i=1\). Set \(\delta(r)=0\) and let \(P(r)=(r)\) be the trivial one-point path. Also, set \(\sigma= (r)\). For each \(x\neq r\), set \(\delta(x)= w(r,x)\) and \(P(x)=(r,x)\). Let \(x\) be a temporary vertex for which \(\delta(x)\) is minimum. Set \(v_2 = x\), and update \(\sigma\) by appending \(v_2\) to the end of it. Increment \(i\).
Inductive Step (Step\(i\), \(i>1\))
If \(i\lt n\), then for each temporary \(x\), let \[\begin{aligned}\end{aligned}\] If this assignment results in a reduction in the value of \(\delta(x)\), let \(P(x)\) be the path obtained by adding \(x\) to the end of \(P(v_i)\).
Let \(x\) be a temporary vertex for which \(\delta(x)\) is minimum. Set \(v_{i+1}=x\), and update \(\sigma\) by appending \(v_{i+1}\) to it. Increment \(i\).

Example 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 . 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.

The 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.

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

Symbols used here

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\infty

infinity
Not a number: "grows without bound" in limits and intervals.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\varepsilon,\ \delta

epsilon, delta
Small positive tolerances in the definition of a limit.

\sigma,\ s,\ \sigma^2

standard deviation, sample s.d., variance
Typical distance from the mean; its square.

P(A),\ P(A \mid B)

probability, conditional probability
Chance of A; chance of A given that B happened.

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\sup,\ \inf

supremum, infimum
Least upper bound, greatest lower bound.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Tente o seu próprio

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mais em Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion–exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs