Chapter 3

Graph Algorithms

In this chapter, we present basic algorithms for graphs.

3.1 Material from Prerequisite Courses

In CSI-2101, you studied graphs and in CSI-2110, you studied data structures related to
graphs. We assume you know the definitions of undirected/directed graphs, degree (outde-
gree/indegree), path, cycle, walk, closed walk, tree, forest, spanning tree, etc. In this section,
we present some important tools you covered in the past. This is not a complete summary,
please refer to your course notes (CSI-2101 & CSI-2110) for a detailed presentation.
In this course, all graphs are assumed to be simple. That is, graphs do not contain loops1
nor parallel edges2 . Another technical but important assumption is that all graphs contain
at least one vertex. The following classical result is useful to analyse the running time of
some graph algorithms.
Theorem 3.1 (Handshaking Lemma). Let G = (V, E) be a graph.
1. If G is undirected, then !
deg(u) = 2|E|.
u→V

2. If G is directed, then
!
indeg(u) = |E|,
u→V
!
outdeg(u) = |E|,
u→V

1
A loop is an edge whose two endpoints are the same.
2
Two edges e and e→ are said to be parallel if the endpoints of e are the same as the endpoints of e→ .

93
 !
deg(u) = 2|E|.
u→V

There are two standard data structures to store a graph: the adjacency matrix representation
and the adjacency list representation.

Adjacency Matrix Representation Consider a graph G = (V, E), where V = {v1 , v2 , ..., vn }.
If G is undirected, the entries of the adjacency matrix A = (ai,j ) satisfy
"
0 if {vi , vj } →↑ E,
ai,j =
1 if {vi , vj } ↑ E.

Since we only consider simple graphs, all entries in the main diagonal are 0. And when G
is undirected, then the matrix is symmetric. Here is an example of an undirected graph
together with the corresponding adjacency matrix.

A F 2A B C D E F3
A 0 1 1 0 0 0
B661 0 1 1 1 077
C E B C661 1 0 1 0 077
D660 1 1 0 0 077
E 40 1 0 0 0 05
D F 0 0 0 0 0 0

For the directed case, consider a graph G = (V, E), where V = {v1 , v2 , ..., vn }. If G is
directed, the entry of the adjacency matrix A = (ai,j ) satisfy
"
0 if (vi , vj ) →↑ E,
ai,j =
1 if (vi , vj ) ↑ E.

Since we only consider simple graphs, all entries in the main diagonal are 0. Here is an
example of a directed graph together with the corresponding adjacency matrix.

A F 2A B C D E F3
A 0 1 0 0 0 0
B660 0 0 1 0 077
C E B C661 1 0 0 0 077
D660 0 1 0 0 077
E 40 1 0 0 0 05
D F 0 0 0 0 0 0

The advantage of the adjacency matrix representation is the following.

• In O(1) time, we can test if there is an edge between two given vertices (simply read
the corresponding entry in the adjacency matrix).

94
The disadvantages of the adjacency matrix representation are the following.
• Uses !(n2 ) space for any graph (even if the graph does not contain any edge!)
• In the undirected case, finding all neighbours of a given vertex v takes !(n) time (even
if deg(v) = 0, you need to scan the entire row/column corresponding to v). In the
directed case, finding all out-neighbours of a given vertex v takes !(n) time (even if
outdeg(v) = 0, you need to scan the entire row/column corresponding to v).

Adjacency List Representation Consider a graph G = (V, E), where V = {v1 , v2 , ..., vn }.
The adjacency list representation of G is made of an array A[1..n], where A[i] contains the
adjacency list of vi (1 ↓ i ↓ n). If G is undirected, the adjacency list of vi is a list of all
neighbours of vi . Here is an example of an undirected graph together with its adjacency list
representation.

A F A B C D E F

B A A B B
C E B C C B C

DD
D
E

Note that in general, the adjacency list of a given vertex v is stored in an arbitrary order.
If G is directed, the adjacency list of vi is a list of all out-neighbours of vi . Here is an example
of an directed graph together with its adjacency list representation.

A F A B C D E F

B D A C B
C E B B

Note that in general, as in the undirected case, the adjacency list of a given vertex v is stored
in an arbitrary order.
The advantages of the adjacency list representation are the following.
• Uses !(|V | + |E|) space.
• In the undirected case, finding all neighbours of a given vertex v takes !(1 + deg(v))
time. In the directed case, finding all out-neighbours of a given vertex v takes !(1 +
deg(v)) time.

95
The disadvantages of the adjacency list representation are the following.
• Testing if {u, v} (or (u, v)) is an edge takes O(1 + deg(u)) time.
• In the directed case, finding all in-neighbours of a vertex u ↑ V takes O(|E| + |V |)
time.
This last observation may seem silly at first sight. Why does it take O(|E| + |V |) time to
find all in-neighbours of a vertex with the adjacency list representation?(!) Remember that
the adjacency list of a given vertex u contains all the out-neighbours of u. The only option
we have to find the in-neighbours of u is to scan the adjacency lists of all other vertices to
see whether or not they are in-neighbours of u. As such, the cost is (using the Handshaking
lemma)
! ! ! !
(1 + deg(v)) ↓ (1 + deg(v)) = 1+ deg(v) = |V | + 2|E| = O(|V | + |E|).
v→V \{u} v→V v→V v→V

In this chapter, we also assume you have some basic knowledge of the following algorithms:
Depth-First Search, Breadth-First Search and Dijkstra. Nevertheless, we will revisit these
algorithms in this chapter and study how we can use/modify them to solve other problems.

3.2 Exploring Undirected Graphs

Let G = (V, E) be an undirected graph. One very natural task in graph algorithms is to
explore G, i.e., visit all vertices of G and gather information about its structure. In this
section, we focus on the exploration of undirected graphs. You already studied the Depth-
First Search algorithm (in CSI-2110) whose task is to visit all vertices of a graph. This
algorithm uses the Explore algorithm as a subroutine. The Explore algorithm visits all

Algorithm 18 Explore(v)
1: visited(v) = true
2: previsit(v) // See later
3: for each edge {u, v} ↑ E do
4: if visited(u) = false then
5: call Explore(u)
6: end if
7: end for
8: postvisit(v) // See later

vertices that are reachable from an input vertex v. It uses an array visited[1..|V |] which
keeps track of the vertices that have or have not been visited yet. Before calling Explore(v),
we need to initialize visited to false for all entries. Look at Lines 2 and 8. For now, we
assume these lines do nothing. Depending on the problem we want to solve, we will replace
(one or both of) these lines by some instruction(s).

96
Here is an example of a graph together with the trace of Explore(A).

A
D A B E
B D
G H C F I J

K L E F G

I C H

J
A B C D E F G H I J K L
visited true true true true true true true true true true false false

In this example, we assume that all adjacency lists are stored in alphabetical order. This
is not the case in general, but this simplifies the presentation of the example. The solid
edges form a tree (a graph that is connected and contains no cycle). These edges are
called tree edges. The dotted edges are called back edges. These edges are not traversed
by Explore because otherwise, they would lead to vertices that have already been visited.
They correspond to the vertices u for which the equality in Line 4 of Explore evaluates to
False (so we do not execute Line 5).

Using Explore, we can then describe the Depth-First Search algorithm (which we will refer
to as DFS).

Algorithm 19 DFS(G)
1: for all v ↑ V do
2: visited(v) = false
3: end for
4: for all v ↑ V do
5: if visited(v) = false then
6: explore(v)
7: end if
8: end for

Here is an example of a graph together with the trace of DFS(G).

97
 A K
D A B E
B D
G H C F I J L

K L E F G

I C H

J
A B C D E F G H I J K L
visited true true true true true true true true true true true true

In this example, we assume that all adjacency lists are stored in alphabetical order. This is
not the case in general, but this simplifies the presentation of this example. The solid edges
form a tree (connected, no cycle). These edges are called tree edges. The dotted edges are
called back edges. These edges are not traversed by Explore because otherwise, they would
lead to vertices that have already been visited. They correspond to the vertices u for which
the equality in Line 4 of Explore evaluates to False (so we do not execute Line 5).
In both previous examples, we have tree edges and back edges. In the first example (the
trace of Explore(A)), the tree edges form a tree and in the second example (the trace of
DFS(G)), the tree edges form a forest which we refer to as the DFS-forest. Each tree in this
DFS-forest is refer to as a DFS-tree. And what about the back edges? In Section 3.3, we will
prove that a graph contains a cycle if and only if the DFS-forest contains a back edge. This
semester, whenever we make the trace of Explore or DFS, we will always draw the edges this
way.
Let us now analyze the running time of DFS. The first for-loop takes O(|V |) time. What
about the second for-loop? To analyze the second for-loop, observe that the sub-routine
explore(u) is called exactly once for each vertex u (this may be part of a recursive call).
The time spent for explore(u), excluding recursive calls, is O(1 + deg(u)). As such, the total
running time of DFS is
# $
!
O |V | + (1 + deg(u)) = O (|V | + |V | + 2|E|) = O(|V | + |E|),
u→V

where we used the Handshaking lemma.

What is the di!erence between the trace of Explore(A) and the trace of DFS(G)? The
algorithm DFS(G) visits all vertices in G. However, Explore(A) visits all (but only the)
vertices in G that are reachable from A. In other words, if G is disconnected, Explore(A)
and DFS(G) do not produce the same trace. We can modify DFS so that it visits all vertices
of G, and, it identifies all connected components of G. We simply work with a counter cc

98
(for connected component) and we change Line 2 of Explore(v) by

previsit(v) ↔ “ccnumber(v) = cc”.

We get the following pseudocode for DFS. The array ccnumber[1..|V |] obviously stores the

Algorithm 20 DFS(G) (connected component version)

1: for all v ↑ V do
2: visited(v) = f alse
3: ccnumber(v) = 0
4: end for
5: cc = 0
6: for all v ↑ V do
7: if visited(v) = f alse then
8: cc = cc + 1
9: explore(v)
10: end if
11: end for

connected component number of each vertex. This modification of DFS does not change its
running time.
Here is a trace of this new version of DFS.

A B C D A C F

E F G H B E D

I J K L I H

J G L

A B C D E F G H I J K L
visited true true true true true true true true true true true true

ccnumber 1 1 2 2 1 3 2 2 1 1 2 2

3.3 Exploring Directed Graphs

Let us turn our attention to directed graphs. In the previous section, we used DFS to identify
the connected components of an undirected graphs. Identifying the connected components of
an undirected graph gives us some information about the structure of this graph. Let us see

99
what we can learn about the structure of a directed graph G using DFS. As we execute DFS,
we will give two numbers to each vertex v: a prenumber and a postnumber. The prenumber
of v corresponds to the time at which we visited v for the first time. The postnumber of v
corresponds to the time at which we completed the exploration of all the vertices that are
reachable from v. We simply work with a counter clock (which we initialize at 1), and then
we change Line 2 of Explore(v) by
previsit(v) ↔ pre(v) = clock
clock = clock + 1
and Line 8 of Explore(v) by
postvisit(v) ↔ post(v) = clock
clock = clock + 1.
The arrays pre[1..|V |] and post[1..|V |] obviously store the pre/post-numbers of all vertices.
We get the following pseudocode for DFS.

Algorithm 21 DFS(G) (pre/post version)

1: for all v ↑ V do
2: visited(v) = f alse
3: pre(v) = ↗
4: post(v) = ↗
5: end for
6: clock = 1
7: for all v ↑ V do
8: if visited(v) = f alse then
9: explore(v)
10: end if
11: end for

Here is an example where, for each vertex, the first integer is its prenumber and the second
integer is its postnumber.

1, 16
B A C A

12, 15
E F D B 2, 11 C

3, 10 13, 14
G H E D

4, 7 F H 8, 9

5, 6 G

100
We see that with directed graphs, we also find a DFS-forest, although here, the DFS-trees
are directed trees. Looking more closely at this example, we again see solid edges and dotted
edges. When dealing with directed graphs, we will give di!erent names to these di!erent
types of edges. As in the undirected case, the solid edges will be called tree edges. They are
the edges we follow when we run DFS. The dotted edges will be split into three di!erent
types: forward edges, back edges and cross edges.

A tree edge is an edge (v, u) where u is a child of v (in the DFS-forest). This implies that
the exploration of u started and ended within the exploration of v. In other words, as we
were running Explore(v), we made a recursive call to Explore(u). Moreover, the exploration
of all vertices reachable from u was over before Explore(v) itself was over. As such, we have

pre(v) < pre(u) < post(u) < post(v). (3.1)

Here is the same example, but this time the tree edges appear in bold.

1, 16
B A C A

12, 15
E F D B 2, 11 C

3, 10 13, 14
G H E D

4, 7 F H 8, 9

5, 6 G

A forward edge is an edge (v, u) where u is a descendant of v (in the DFS-forest) but u is
not a child of v. The situation here is quite similar to the one for tree edges. If we found a
forward edge, this means that the exploration of u started and ended within the exploration
of v. In other words, as we were running Explore(v), we made a recursive call to Explore(u)
(from one of the descendants of v). Moreover, the exploration of all vertices reachable from
u was over before Explore(v) itself was over. As such, we have

pre(v) < pre(u) < post(u) < post(v). (3.2)

Here is the same example again, but this time the forward edges appear in bold.

101
 1, 16
B A C A

12, 15
E F D B 2, 11 C

3, 10 13, 14
G H E D

4, 7 F H 8, 9

5, 6 G

A back edge is an edge (v, u) where v is a descendant of u (in the DFS-forest). This implies
that the exploration of v started and ended within the exploration of u. In other words,
as we were running Explore(u), we made a recursive call to Explore(v) (from one of the
descendants of u). Moreover, the exploration of all vertices reachable from v was over before
Explore(u) itself was over. As such, we have

pre(u) < pre(v) < post(v) < post(u). (3.3)

Here is the same example again, but this time the back edges appear in bold.

1, 16
B A C A

12, 15
E F D B 2, 11 C

3, 10 13, 14
G H E D

4, 7 F H 8, 9

5, 6 G

The cross edges are all the other edges. A cross edge (v, u) crosses over from one subtree (of
the DFS-forest) to a di!erent subtree (of the DFS-forest). This means that the exploration
of u started and ended before v was even discovered. Then, the exploration of v started, and
eventually ended. That is, Explore(u) was called and eventually terminated, and, afterwards,
Explore(v) was called and eventually terminated. As such, we have

pre(u) < post(u) < pre(v) < post(v). (3.4)

Here is the same example again, but this time the cross edges appear in bold.

102
 1, 16
B A C A

12, 15
E F D B 2, 11 C

3, 10 13, 14
G H E D

4, 7 F H 8, 9

5, 6 G

We can modify DFS so that it gives a label tree/forward/back/cross to each edge without
increasing the running time. Exercise 19 asks you to explain how to do that.
An important thing to notice is that the trace of DFS depends on the order in which the
adjacency lists are stored. Let us look at the same example once more, but this time,
assume the adjacency lists are stored using the reverse alphabetical order. Then we obtain
the following DFS-forest...

1, 4 5, 10 11, 16
B A C H F D

E F D 2, 3 G B 6, 9 12, 15 A

G H E 7, 8 13, 14 C

quite di!erent, isn’t it? But it is still the same graph! Only the adjacency lists are di!erent.
(Can you identify all types of all edges?)
We are now ready for the following lemma.
Lemma 6. Let G = (V, E) be a directed graph3 . Then

G is cyclic if and only if the DFS-forest of G has a back-edge.

Proof. [↘≃] Suppose G is cyclic. Then G has a cycle v0 , v1 , v2 , ..., vk , v0 . Consider the DFS-
forest of G. We may assume that v0 has the smallest pre-number (otherwise simply relabel
the vertices.) This means that all of explore(v1 ), explore(v2 ),..., explore(vk ) are called inside
of explore(v0 ). This implies that pre(v0 ) < pre(vk ).
Now consider the edge (vk , v0 ). Since pre(v0 ) < pre(vk ), then by the definition of back-edge,
(vk , v0 ) is a back edge.
3
Where the adjacency lists are stored with respect to any fixed order.

103
[⇐↘] Suppose G has a back-edge (v, u). By the definition of back-edge, there is a sequence
of tree edges from u to v. Then the sequences of tree edges from u to v, followed by the edge
(v, u) is a cycle.

Observe that Lemma 6 holds for undirected graphs as well.

Using Lemma 6, it is now very simple to test whether or not a given directed graph is cyclic
or acyclic.

• Run DFS (including pre/post-numbers & edge classification)

• Look for a back edge.

– As soon as we find a back edge, we return “cyclic” and we stop.

– At the end, if we have not found any back edge, we return “acyclic” and we stop.

This takes O(|V | + |E|) time.

But wait! How do we identify the type of each edge? How do we do that e"ciently? We can
modify DFS(G) and Explore(v) in the following way.

Algorithm 22 DFS(G) (edge type version)

1: for v ↑ V do
2: pre(v) = ↗
3: post(v) = ↗
4: end for
5: clock = 1
6: for v ↑ V do
7: if pre(v) = ↗ then
8: explore(v)
9: end if
10: end for

104
Algorithm 23 explore(v) (edge type version)
1: pre(v) = clock
2: clock = clock + 1
3: for all edges e = (v, u) do
4: if pre(u) = ↗ then
5: Report e as a tree edge.
6: explore(u)
7: else if post(u) < pre(v) then
8: Report e as a cross edge.
9: else if pre(u) < pre(v) then
10: Report e as a back edge.
11: else
12: Report e as a forward edge.
13: end if
14: end for
15: post(v) = clock
16: clock = clock + 1

In this version of DFS(G) all pre/post-numbers are initialized at ↗. We know that when
the algorithm is over, all pre/post-numbers will be between 1 and 2|V |. Therefore, a vertex
has been visited if and only if its pre-number is di!erent than ↗. This is the purpose of
Line 7. As such, we no longer need the array visited[1..|V |].

Now let us have a closer look at the new version of Explore(v). The purpose of Line 4 is to
test whether the edge e = (v, u) has already been traversed. If not, then we just discovered
a tree edge! Otherwise what is the algorithm doing? The only edge type for which the
inequality post(u) < pre(v) is true is the cross edge. As such, if the test of Line 7 is true,
then we just discovered a cross edge. If this test is false as well, then e = (v, u) can only
be a back edge or a forward edge. Among these two types of edges, the only one for which
the inequality pre(u) < pre(v) is true is the back edge. As such, if the test of Line 9 is true,
then we just discovered a back edge. Finally, if this third test is also false, there is only one
option left: we discovered a forward edge.

The analysis of Section 3.2 still holds for the running time of these new versions of DFS(G)
and Explore(v). We still spend O(1 + deg(v)) for each call to Explore(v) (excluding the
recursive calls) and Explore is called exactly once for each vertex. Thus, we get a running
time of O(|V | + |E|).

105
3.3.1 Topological Ordering
Consider the following sculpture that has just been ordered by the National Gallery of
Canada4 .

I
E
D

C
H

A F G

Unfortunately, it was shipped unassembled. As such, the employees of the museum will have
to assemble it. The following graph shows what piece stands on what other piece.

C
B

H
G

4
This was made by a famous artist named Zelazouane

106
From this graph, it should be possible to figure out how to assemble the sculpture (for
instance, one cannot install H before installing G). Actually, if we reverse all edges, we can
see what piece has priority on what other piece.

C
B

H
G

From this graph, we see that installing the pieces in the following order will work: A, F , G,
B, H, C, D, E, I. If we redraw the graph with respect to this ordering, we find the following
representation.

A F G B H C D E I

This ordering is called a topological ordering of the graph.

Consider a directed and acyclic graph G = (V, E). Formally speaking, a topological ordering
of G is an ordering of the vertices such that, if (u, v) is an edge, then u appears before v in
the ordering.
There can be more than one topological ordering for a given graph. For instance, in our
sculpture problem, we could also assemble the pieces in the following order and everything
would be fine: G, H, A, F , B, C, D, E, I.
Do you see why we need the graph to be acyclic? Assume we have the following cycle in a
directed graph: a, b, c, d, e, a. Then the definition of topological ordering asks for a to appear
before b which must appear before c, which must appear before d, which must appear before
e, which must appear before a. Obviously, we cannot make a appear before itself!

107
In this section, we want to solve the following problem.

INPUT: A directed and acyclic graph G = (V, E)

OUTPUT: A topological ordering of G

We will assign a number #(u) to each vertex u ↑ V which will give the ordering. In
other words, we will give a number to each vertex of G such that, if (u, v) is an edge, then
#(u) < #(v).

Here is an algorithm which will succeed. It simply chooses the vertex that has lowest priority
at each iteration.

Algorithm T opologicalOrdering(G)
Input: A directed acyclic graph G = (V, E)
Output: A topological ordering of V
1: k = 1
2: while V →= { } do
3: Choose a vertex u ↑ V with indegree 0.
4: Give u the number k.
5: k =k+1
6: Remove u from G.
7: end while

Here is a trace of this algorithm.

108
 A C E A C E B gets number 1.
Remove B from the graph.
B D F D F

We can pick A or D.
C E C E D gets number 3.
Let us choose A.
Remove D from the graph.
D F A gets number 2. F
Remove A from the graph.

We can pick E or F .
E C gets number 4.
Let us choose E.
Remove C from the graph.
F F E gets number 5.
Remove E from the graph.

F gets number 6. We get the following ordering.

Remove F from the graph.
B A D C E F
1 2 3 4 5 6

Instead of analysing the running time of this algorithm, we present another one, right away.
This other algorithm is very simple and its running time is optimal.
Assume that G = (V, E) is a directed acyclic graph.
Step 1 : Run DFS (including pre/post-numbers)
Step 2 : Run Bucket Sort to sort the vertices by postnumber.
Step 3 : Obtain the topological ordering from the reverse sorted order of the postnumbers.
We need to answer two important questions. (1) What is the running time of this algorithm
and (2) whyis this algorithm correct?
In order to find the running time of this algorithm, let us try to figure out how much time
it takes for Bucket Sort. The post-numbers are between 1 and 2n, where n = |V |. In this
case Bucket Sort does the following. It initializes an array A[1..(2n)] of size 2n with 0’s
in all entries. Then, it scans the post-numbers and whenever it finds a number x, it does
A[x] = A[x] + 1. At the end, it simply reads A in order from A[1] to A[2n]. Initializing
A takes O(2n) = O(n) time, scanning the post-numbers (and updating A) takes O(n) time
and reading A at the end takes O(2n) = O(n) time. So in total, in this algorithm, Bucket
Sort takes O(n) time.
So in total, the running time of this topological ordering algorithm is O(|V | + |E|).
We have to be careful with Bucket Sort. Many people make the following wrong reasoning.

109
 We can sort an array B[1..n] of n numbers in O(n) time in the following way. Find the
maximum element xmax of A (this takes O(n) time). Then initialize an array A[1..xmax ] of
size xmax with 0’s in all entries (this takes O(n) time). Then, scan B and whenever you
find a number x, do A[x] = A[x] + 1 (this takes O(n) time). At the end, simply read A in
order (this takes O(n) time). So in total, this takes O(n) time.

Where is the mistake in this reasoning? Initializing A does not take O(n) time. Reading A
at the end does not take O(n) time. Each of these two steps takes O(xmax ) time. And the
problem is that xmax is independent
% of n. In& general, we do not have xmax = O(n). Indeed,
1000
look at the following array: 1, 1, 1, 1, 22 . To summarize, sorting an array of n numbers
using bucket sort, where the maximum element is xmax ⇒ n takes O(xmax ) time.
In the topological ordering algorithm we presented, we know that the maximum postnumber
is at most 2n. As such, we get O(2n) = O(n) time for the Bucket Sort step.
Here is a trace of our second algorithm.

1, 8 9, 12
A C E A B

2, 7 10, 11
B D F C D

3, 4 5, 6
E F

By sorting the vertices by postnumber, we get E, F, C, A, D, B. Therefore, we get the fol-

lowing topological ordering.

B D A C F E
# 1 2 3 4 5 6

We now need to explain whi this algorithm is correct.

Lemma 7. When we sort the vertices in reverse order of their postnumbers, we get a topo-
logical of the graph.

Proof. We want to prove that for every edge (v, u), we have #(v) < #(u), i.e., for every edge
(v, u), we have post(v) > post(u) (remember... reverse order of postnumbers). We prove it
by contradiction.
Suppose there is an edge (v, u) for which post(v) < post(u). In this case, (v, u) does not
satisfy the inequalities for a tree edge, a forward edge or a cross edge. As such, (v, u) is
not a tree edge, a forward edge or a cross edge. Therefore, (v, u) must be a back edge. But
then the graph is cyclic by Lemma 6 and does not admit a topological ordering. This is a
contradiction.

110
3.4 Shortest Paths
In this section, we study shortest paths (in graphs, of course). In a graph, the length of
a path can be measured in many di!erent ways. When the length of a path between two
vertices u and v corresponds to the number of edges along that path, we sometimes talk
about the hop-distance between u and v. If each edge has a weight, then the length of a
path is the sum of the lengths of the edges along that path. In this case, we talk about a
weighted graph.

A weighted graph is a graph G = (V, E), where each edge e has a weight wt(e) > 0. This
definition applies both to undirected and directed graphs. Moreover, nothing in the definition
requires that the graph is connected. If there is no edge between (from) a vertex u and (to)
a vertex v, we sometimes say that the edge (that does not exist!) has weight ↗. The weight
(or the length) of a path is the sum of the weights of the edges along that path. And of
course, a shortest path between two vertices u and v is a path between u and v whose length
is minimum. Here are two examples of weighted graphs (one undirected and one directed).

12 12 14 5
A B C D A B C D
4 8 2 3
3 1 1

E F 1 G H E 6 F G 4 H

In this section, given a weighted graph G = (V, E) and two vertices u, v ↑ V , we denote the
length of a shortest path from u to v by ω(u, v).

When an undirected graph is stored using adjacency lists, the weight of an edge {u, v} is
stored together with v in u’s adjacency list and it is stored together with u in v’s adjacency
list. When a directed graph is stored using adjacency lists, the weight of an edge (u, v) is
stored together with v in u’s adjacency list. Here are the adjacency list representations of
the previous two examples.

A B C D E F G H A B C D E F G H

B,12 A,12 B,12 B,7 A,3 G,1 A,4 C,2 B,14 F,1 D,5 E,6 D,1

E,3 C,12 H,2 B,8 H,3 G,4

G,4 D,7 F,1

G,8

111
When an undirected graph is stored using the adjacency matrix representation5 , the weight
of an edge {u, v} is stored both at Adj[u][v] and at Adj[v][u]. If there is no edge between two
vertices, then we store the value ↗. When a directed graph is stored using the adjacency
matrix representation, the weight of an edge (u, v) is stored at Adj[u][v]. If there is no edge
from a given vertex to another vertex, then we store the value ↗. Here are the adjacency
list representations of the previous two examples.
   
0 12 ↗ ↗ 3 ↗ 4 ↗ 0 14 ↗ ↗ ↗ ↗ ↗ ↗
12 0 12 7 ↗ ↗ 8 ↗ ↗ 0 ↗ ↗ ↗ 1 ↗ 3 
   
↗ 12 0 ↗ ↗ ↗ ↗ 2  ↗ ↗ 0 5 ↗ ↗ ↗ ↗
   
↗ 7 ↗ 0 ↗ ↗ ↗ ↗ ↗ ↗ ↗ 0 ↗ ↗ ↗ ↗
   
 3 ↗ ↗ ↗ 0 ↗ ↗ ↗ ↗ ↗ ↗ ↗ 0 ↗ ↗ ↗
   
↗ ↗ ↗ ↗ ↗ 0 1 ↗ ↗ ↗ ↗ ↗ 6 0 ↗ ↗ 
   
 4 8 ↗ ↗ ↗ 1 0 ↗ ↗ ↗ ↗ ↗ ↗ ↗ 0 ↗
↗ ↗ 2 ↗ ↗ ↗ ↗ 0 ↗ ↗ ↗ 1 ↗ ↗ 4 0

In this section, we want to solve the following problem.

INPUT: A weighted directed graph G = (V, E) together with a source vertex s ↑ V .

OUTPUT: An array d[1..|V |] such that for all 1 ↓ i ↓ |V |, d[i] = ω(s, i).

If all weights are equal, this is easy: use Breadth-first search. Otherwise, the solution to
this problem is the well-known Dijkstra’s algorithm. The general approach for Dijkstra’s
algorithm is the following. For each vertex v ↑ V , we maintain variable

d(v) = length of a shortest path from s to v found so far .

At start, we have "

0 if v = s,
d(v) =
↗ if v →= s.

At each iteration, we pick a vertex u for which d(u) = ω(s, u). For each edge (u, v), we
update d(v) in the following way:

d(v) = min {d(v), d(u) + wt(u, v)} .

shortest path from s to u

s u

v
current best path from s to v
5
As we already mentioned at the beginning of this chapter, unless stated otherwise, we assume that all
graphs this semester are stored using the adjacency list representation.

112
The hope is that at the end, for all vertices v ↑ V , we have d(v) = ω(s, v). But how do we
choose u? How do we know whether or not d(u) = ω(s, u)?

Let us maintain a set S ⇑ V such that for all v ↑ S,

d(v) = ω(s, v), i.e., we know ω(s, v).

S Q=V \S

(s, v) (s, v) has not been

has been computed yet
computed

At start, we have

S = ⊋,
Q = V,
d(s) = 0,
d(v) = ↗ for each vertex v →= s.

At each iteration, grow S by moving one vertex u from Q to S. Which vertex u do we move?
At start, this is easy: we know that d(s) = 0 = ω(s, s). Thus, at start, we move s from
Q to S. Then, at each subsequent iteration, we choose the vertex u ↑ Q for which d(u) is
minimum. Later, we will prove that for this vertex u, we have d(u) = ω(s, u). Then for each
edge (u, v), we update d(v) in the following way:

d(v) = min {d(v), d(u) + wt(u, v)} .

We get the following algorithm.

113
Algorithm Dijkstra(G, s)
1: for each vertex v ↑ V do
2: d(v) = ↗
3: end for
4: d(s) = 0
5: S = { }
6: Q = V
7: while Q →= { } do
8: u = vertex in Q for which d(u) is minimum (we will prove later that d(u) = ω(s, u))
9: delete u from Q
10: insert u into S
11: for each edge (u, v) do
12: d(v) = min {d(v), d(u) + wt(u, v)}
13: end for
14: end while

Here is the trace of Dijkstra on the following graph.

1
t x
10 3
2 6
s 4
9
5
y z
2
7

Q s t x y z V s t x y z
S=⊋
d 0 ↗ ↗ ↗ ↗ d 0 ↗ ↗ ↗ ↗
• u=s
• ω(s, s) = d(s) = 0
• delete s from Q
• update d(t) and d(y)

Q t x y z V s t x y z
S = {s}
d 10 ↗ 5 ↗ d 0 10 ↗ 5 ↗
• u=y
• ω(s, y) = d(y) = 5
• delete y from Q
• update d(t), d(x) and d(z)

114
 Q t x z V s t x y z
S = {s, y}
d 8 14 7 d 0 8 14 5 7
• u=z
• ω(s, z) = d(z) = 7
• delete z from Q
• update d(x) and d(s)

Q t x V s t x y z
S = {s, y, z}
d 8 13 d 0 8 13 5 7
• u=t
• ω(s, t) = d(t) = 8
• delete t from Q
• update d(x) and d(y)

Q x V s t x y z
S = {s, t, y, z}
d 9 d 0 8 9 5 7
• u=x
• ω(s, x) = d(x) = 9
• delete x from Q
• update d(z)

V s t x y z
S = {s, t, x, y, z} Q=⊋
d 0 8 9 5 7

And we are done!

What is the running time of Dijkstra? Let n = |V | and m = |E|. Store Q in a min-heap,
where the key of each vertex is d(v). The running time for the initialization phase is O(n)
(including the time to build the heap storing Q = V ).
Let us consider one iteration.
• Find u and delete it from Q.

extract_min : O(log(n)) time

• For each edge (u, v), we update d(v)

decrease_key : O(log(n)) time

115
Thus, the total time for one iteration is

O(log(n)) + O(outdegree(u) · log(n)).

Therefore, the total running time of Dijkstra is

# $
!
O(n) + O (log(n) + outdegree(u) · log(n))
u→V
# $
!
= O(n) + O log(n) (1 + outdegree(u))
u→V
= O(n) + O (log(n)(n + m))
= O ((m + n) log(n)) .

Using a data structure called Fibonacci Heap to store Q, we can do O(n log(n) + m) time.

3.4.1 Proof of Correctness of Dijkstra

One important question is how do we prove that Dijkstra correctly solves the shortest path
problem?
(to be completed)

116