Chapter 22

Dijkstra’s Algorithm

Philip W. L. Fong

Department of Computer Science

University of Calgary
Calgary, Alberta, Canada

CPSC 331 (Fall 2025)

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Readings

Chapter 22: Single-Source Shortest Paths

Introductory materials in the beginning of the chapter, on
pages 604–612.
§22.3: Dijkstra’s algorithm
§22.5: Proofs of shortest-paths properties

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Weighted Directed Graphs
a directed graph G = (V , E)
a weight function w : E → R≥0 mapping each edge to a
nonnegative weight
Example: distance between cities

t X
I
g
lo
ar tr
Z 3 9
S 46
T
5 j 7
j
j
z
Y Z
Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm
Path Weight
The weight of a path p = ⟨v0 , v1 , . . . , vk ⟩ is:
k
X
w(p) = w(vi−1 , vi )
i=1

t X
I
g
lo
ar tr
Z 3 9
S 46
T
5 j 7
j
j
z
Y Z
Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm
Example: Path Weight
t X
I
g
lo
ar tr
Z 3 9
S 46
T
5 j 7
j
j
z
Y Z

What is the weight of the following paths?

s, t, x
s, y , x
s, y , z, x
s, y , t, x
Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm
Initialization
Algorithm 1: I NITIALIZE -S INGLE -S OURCE(G, s)
1 for v ∈ G.V do
2 v .dist = ∞;
3 v .pred = NIL;
4 [Link] = 0;

t X
I
g
lo
ar tr
Z 3 9
S 46
T
5 j 7
j
j
z
Y Z

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Relaxation

Algorithm 2: R ELAX(u, v , w)
1 if v .dist > [Link] + w(u, v ) then
2 v .dist = [Link] + w(u, v );
3 v .pred = u;

u v

5
2 /9
Before:

5
2 /7
After:

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Relaxation

Algorithm 3: R ELAX(u, v , w)
1 if v .dist > [Link] + w(u, v ) then
2 v .dist = [Link] + w(u, v );
3 v .pred = u;

u v

5
2 /6
Before:

5
2 /6
After:

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Generic Algorithm for Single-Source Shortest Paths

Algorithm 4: G ENERIC -S INGLE -S OURCE(G, w, s)

1 I NITIALIZE -S INGLE -S OURCE(G, s);
2 while distance estimates have not converged do
3 select an edge (u, v ) from G.E;
4 R ELAX(u, v , w);

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Illustration

Relaxation Sequence:

(s, y ), (y , x), (y , z), (z, x), (s, t), (t, x), (y , t), (t, x)

Predecessor Tree
t X
I
g
lo
ar tr
Z 3 9
S 46
T
5 j 7
j
j
z
Y Z

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Observations about the Generic Algorithm

Observation
The following are loop invariants:
The predecessor pointers form a tree.
v .dist ≥ δ(s, v ).
In addition, the following statements hold:
v .dist never increases: i.e., when the value of v .dist is
changed, it is changed to a strictly smaller value.
Once v .dist becomes δ(s, v ), it stays with that value
without change. At that point, the path in the predecessor
tree from s to v is a shortest path, and v .dist is its length.
If p = ⟨v0 , v1 , . . . , vk ⟩ is a shortest path from s = v0 to vk ,
and we relax the edges of p in the order (v0 , v1 ), (v1 , v2 ),
. . . , (vk −1 , vk ), then vk .dist = δ(s, vk ).

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Problem with Generic Algorithm

How do we know the process will converge?

Are we converging in the fastest possible pace?

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Enter Dijkstra’s Algorithm

Dijkstra’s algorithm is an instantiation of the generic algorithm:

It attends to vertices one at a time.
It chooses to attend to the vertex u with the minimum
[Link].
When it attends to u, it relaxes all edges (u, v ) ∈ E.
Once u has been attended to, it will never be attended to
again.

Termination is obvious.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Dijkstra’s Algorithm

Algorithm 5: D IJKSTRA(G, w, s)
1 I NITIALIZE -S INGLE -S OURCE(G, s);
2 S = ∅;
3 Q = G.V ;
4 while Q ̸= ∅ do
5 u = E XTRACT-M IN(Q);
6 S = S ∪ {u};
7 for v ∈ [Link][u] do
8 R ELAX(u, v , w);

The lines in blue are only for establishing correctness.

They do not contribute to the computation of shortest
paths.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Illustration

t X
I
g
lo
ar tr
Z 3 9
S 46
T
5 j 7
j
j
z
Y Z

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Issues of Correctness

Are the paths in the predecessor tree shortest paths?

Are the distance estimates the real distances?

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Correctness

Theorem
For every vertex v in the predecessor tree T , the sv -path in T
is a shortest path in G.

Corollary
v .dist = δ(s, v ) for every v in the predecessor tree.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Suppose the following is a shortest sv ∗ -path:

⟨s, u1 , u2 , . . . , un−1 , v ∗ ⟩

The weight of this path is δ(s, v ∗ ) ≤ v ∗ .dist.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Suppose the following is a shortest sv ∗ -path:

⟨s, u1 , u2 , . . . , un−1 , v ∗ ⟩

The weight of this path is δ(s, v ∗ ) ≤ v ∗ .dist.

Consider the iteration in which v ∗ is removed from Q.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Suppose the following is a shortest sv ∗ -path:

⟨s, u1 , u2 , . . . , un−1 , v ∗ ⟩

The weight of this path is δ(s, v ∗ ) ≤ v ∗ .dist.

Consider the iteration in which v ∗ is removed from Q.
Let i be the biggest index for which ui ∈ S but ui+1 ̸∈ S.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Suppose the following is a shortest sv ∗ -path:

⟨s, u1 , u2 , . . . , un−1 , v ∗ ⟩

The weight of this path is δ(s, v ∗ ) ≤ v ∗ .dist.

Consider the iteration in which v ∗ is removed from Q.
Let i be the biggest index for which ui ∈ S but ui+1 ̸∈ S.
ui+1 is laying on a shortest path. Thus,

ui+1 .dist = δ(s, ui+1 ) ≤ δ(s, v ∗ ) ≤ v ∗ .dist

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Suppose the following is a shortest sv ∗ -path:

⟨s, u1 , u2 , . . . , un−1 , v ∗ ⟩

The weight of this path is δ(s, v ∗ ) ≤ v ∗ .dist.

Consider the iteration in which v ∗ is removed from Q.
Let i be the biggest index for which ui ∈ S but ui+1 ̸∈ S.
ui+1 is laying on a shortest path. Thus,

ui+1 .dist = δ(s, ui+1 ) ≤ δ(s, v ∗ ) ≤ v ∗ .dist

But v ∗ is removed from Q rather than ui+1 , meaning:

ui+1 .dist ≥ v ∗ .dist

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm

Proof
If the sv -path in the predecessor tree is not a shortest path from s to v , we say
that v is a violation. Choose v ∗ to be the earliest violation to be added to S.
Let the sv ∗ -path in the predecessor tree be the following:

⟨s, v1 , v2 , . . . , vm−1 , v ∗ ⟩

The weight of this path is v ∗ .dist.

Suppose the following is a shortest sv ∗ -path:

⟨s, u1 , u2 , . . . , un−1 , v ∗ ⟩

The weight of this path is δ(s, v ∗ ) ≤ v ∗ .dist.

Consider the iteration in which v ∗ is removed from Q.
Let i be the biggest index for which ui ∈ S but ui+1 ̸∈ S.
ui+1 is laying on a shortest path. Thus,

ui+1 .dist = δ(s, ui+1 ) ≤ δ(s, v ∗ ) ≤ v ∗ .dist

But v ∗ is removed from Q rather than ui+1 , meaning:

ui+1 .dist ≥ v ∗ .dist

Thus, v ∗ .dist = δ(s, v ∗ ), a contradiction to the assumption that v ∗ is a violation.

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm
Running Time

Assume that the priority queue Q is a binary heap.

I NITIALIZE -S INGLE -S OURCE involves creating a min-heap
from scratch: O(V )
Each vertex is returned at most once from E XTRACT-M IN:
O(V lg V )
R ELAX involves an implicit invocation of D ECREASE -K EY:
O(E lg V )
Overall: O((V + E) lg V )
= O(E lg V ) if E = Ω(V )

Philip W. L. Fong Chapter 22: Dijkstra’s Algorithm