Shortest Path Problems

Discrete Mathematics

Shortest Path Problems 1

Weighted Graphs

Graphs that have a number assigned to each edge are called

weighted graphs.
A more mathematical definition: A weighted graph is a graph
G = (V , E , w ), where V is a set of vertices, E is a set of edges
between vertices of V , and w is a function from V × V into R.
The function w gives to each pair of vertices a weight in R.
Note 1: Usually w (u, v ) are positives for all pairs of vertices.
Note 2: Usually w (u, v ) = ∞ if the pair of vertices (u, v ) is not an
edge of E .

Shortest Path Problems 2

Length of a Path

Let the path p, form vertices a to z, be given by the sequence of

edges e1 , e2 , ..., en of the graph, such that f (e1 ) = (a, x1 ),
f (e2 ) = (x1 , x2 ), ..., f (en ) = (xn−1 , z).
The length L(p) of a path p, in a weighted graph, is the sum of
the weights of the edges of this path, i.e.
L(p) = w (a, x1 ) + w (x1 , x2 ) + · · · + w (xn−1 , z).
A common problem is to find the path, with minimal length,
between two given vertices of a weighted graph.

Shortest Path Problems 3

Edsger Wybe Dijkstra

Rotterdam, 11 May 1930 – 6 August

2002
was a Dutch computer scientist.
He received the 1972 Turing Award
for fundamental contributions to
developing programming languages.
Among his contributions to com-
puter science is the shortest path-
algorithm, also known as Dijkstra’s al-
gorithm and Reverse Polish Notation.
www.cs.utexas.edu/users/EWD

Shortest Path Problems 4

Dijkstra’s Algorithm

procedure Dijkstra (G : a simple connected weighted graph with

with positive weights.
a: initial vertex. z: final vertex)
L(v ) := ∞ for all vertices v of G .
L(a) := 0
S := ∅
while z ∈ /S
begin
u := a vertex not in S with smallest L(u).
S := S ∪ {u}
for all vertex v not in S
if L(u) + w (u, v ) < L(v )
then L(v ) := L(u) + w (u, v )
end
{L(z) = length of the shortest path from a to z}

Shortest Path Problems 5

Example of Dijkstra’s Algorithm, Step 1 of 8

Consider the following simple connected weighted graph. What is

the shortest path between vertices a and z.
b d f g
6 2 10 1
2 15 4
1 10 3
a c e z

L(v ) is set ∞ for all vertices v of G , L(a) is set to 0 and S to ∅.

b, ∞() d, ∞() f , ∞() g , ∞()
6 2 10 1
2 15 4
1 10 3
a, 0(a) c, ∞() e, ∞() z, ∞()

Shortest Path Problems 6

Example of Dijkstra’s Algorithm, Step 2 of 8

a is the vertex u not in S such that L(u) is minimal.

b, ∞() d, ∞() f , ∞() g , ∞()
6 2 10 1
2 15 4
1 10 3
a, 0(a) c, ∞() e, ∞() z, ∞()

S = S ∪ {a} and L(v ) is updated for all vertex v not in S (and

adjacent to a).
b, 6(a, b) d, ∞() f , ∞() g , ∞()
2 10 1
S 6 2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, ∞() z, ∞()
Note: To save space, L(a, c) = 1, the length of the path through
vertices a and c, is denoted 1(a, c).

Shortest Path Problems 7

Example of Dijkstra’s Algorithm, Step 3 of 8

c is the vertex u not in S such that L(u) is minimal.

b, 6(a, b) d, ∞() f , ∞() g , ∞()
2 10 1
S 6 2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, ∞() z, ∞()

S = S ∪ {c} and L(v ) is updated for all vertex v not in S (and

adjacent to c).
b, 6(a, b) d, 3(a, c, d) f , 16(a, c, f ) g , ∞()
2 10 1
S 6 2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 11(a, c, e) z, ∞()
Note: To save space, L(a, c, d) = 3, the length of the path
through vertices a, c and d, is denoted 3(a, c, d).

Shortest Path Problems 8

Example of Dijkstra’s Algorithm, Step 4 of 8

d is the vertex u not in S such L(u) is minimal.

b, 6(a, b) d, 3(a, c, d) f , 16(a, c, f ) g , ∞()
2 10 1
S 6 2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 11(a, c, e) z, ∞()

S = S ∪ {d} and L(v ) is updated for all vertex v not in S (and

adjacent to d).
b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , ∞()
S 6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 11(a, c, e) z, ∞()

Shortest Path Problems 9

Example of Dijkstra’s Algorithm, Step 5 of 8

f is the vertex u not in S such L(u) is minimal.

b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , ∞()
S 6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 11(a, c, e) z, ∞()

S = S ∪ {f } and L(v ) is updated for all vertex v not in S (and

adjacent to f ).
b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 15(a, c, d, f , g )
S 6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e) z, ∞()

Shortest Path Problems 10

Example of Dijkstra’s Algorithm, Step 6 of 8

b is the vertex u not in S such that L(u) is minimal.

b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 15(a, c, d, f , g )
S 6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e) z, ∞()

S = S ∪ {b} and L(v ) is updated for all vertex v not in S (and

adjacent to b) (in this case, there is not vertex to update).
b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 15(a, c, d, f , g )
S
6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e) z, ∞()

Shortest Path Problems 11

Example of Dijkstra’s Algorithm, Step 7 of 8

e is the vertex u not in S such that L(u) is minimal.

b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 15(a, c, d, f , g )
S
6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e) z, ∞()

S = S ∪ {e} and L(v ) is updated for all vertex v not in S (and

adjacent to e).
b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 15(a, c, d, f , g )
S
6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e) z, 12(a, c, d, f , e, z)

Shortest Path Problems 12

Example of Dijkstra’s Algorithm, Step 8 of 8

z is the vertex u not in S such that L(u) is minimal.

b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 15(a, c, d, f , g )
S
6 2 10 1
2 15 4
1 10 3
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e) z, 12(a, c, d, f , e, z)

S = S ∪ {z} and L(v ) is updated for all vertex v not in S (and

adjacent to z). The algorithm stops here because z ∈ S.
b, 6(a, b) d, 3(a, c, d) f , 5(a, c, d, f ) g , 13(a, c, d, f , e, z, g )
S 6 2 10 1
2 15 4
1 10 3 z, 12(a, c, d, f , e, z)
a, 0(a) c, 1(a, c) e, 9(a, c, d, f , e)

Shortest Path Problems 13

Properties of Dijkstra’s Algorithm

Algorithm Finiteness
Theorem: Dijkstra’s algorithm always ends in n steps or less for a
connected undirected weighted graph withn vertices.
Algorithm Correctness
Theorem: Dijkstra’s algorithm finds the length of a shortest path
between two vertices in a connected undirected weighted graph.
Algorithm Effectiveness
Theorem: Dijkstra’s algorithm uses O(n2 ) operations (additions
and comparisons) to find the length of a shortest path between two
vertices in a connected undirected weighted graph with n vertices.

Shortest Path Problems 14

Floyd’s Algorithm

Floyd’s algorithm can be used to find the length of the shortest

path between all pairs of vertices in a weighted connected simple
graph. However, this algorithm cannot be used to construct
shortest paths.
Robert W. Floyd. “Algorithm 97: Shortest path”, Comm ACM, vol
5 (June 1962), p. 345-.

Shortest Path Problems 15

Floyd’s Algorithm

procedure Floyd (G : weighted simple graph

with vertices v1 , v2 , ..., vn
and weights w (vi , vj ).)
for i := 1 to n
for j := 1 to n
d(vi , vj ) = w (vi , vj )
d(vi , vj ) = ∞ if {vi , vj } is not an edge
for i := 1 to n
for j := 1 to n
for k := 1 to n
if d(vj , vi ) + d(vi , vk ) < d(vj , vk )
then d(vj , vk ) := d(vj , vi ) + d(vi , vk )
{d(vi , vj ) is the length of the shortest path between vi and vj }

Shortest Path Problems 16

Floyd’s Algorithm
Use Floyd’s algorithm to find the distance between all pairs of
vertices in the weighted graph:
b 5 d
4 6 f
a 1 8 2
2 3
c 10 e
We can represent the distances with a 6 × 6 matrix, with
alphabetic order. Initially it is

∞ 4 2 ∞ ∞ ∞
 
 4 ∞ 1 5 ∞ ∞ 
 
 2 1 ∞ 8 10 ∞ 
 
 ∞ 5 8 ∞ 2 6 
 
 ∞ ∞ 10 2 ∞ 3 
∞ ∞ ∞ 6 3 ∞

Shortest Path Problems 17

Floyd’s Algorithm
After completion of the main loop for i = 1 (vertex a), the matrix
is (boxed values are those that were updated)
∞ 4 2 ∞ ∞ ∞
 
 4 8
 1 5 ∞ ∞  
 2 1
 4 8 10 ∞  .
 ∞ 5 8 ∞ 2 6 
 
 ∞ ∞ 10 2 ∞ 3 
∞ ∞ ∞ 6 3 ∞
After completion of the main loop for i = 2 (vertex b), the matrix
is  
8 4 2 9 ∞ ∞
 4
 8 1 5 ∞ ∞  
 2 1 2 6 10 ∞ 
 
 .
 9 5 6 10 2 6 
 
 ∞ ∞ 10 2 ∞ 3 
∞ ∞ ∞ 6 3 ∞
Shortest Path Problems 18
Floyd’s Algorithm
After completion of the main loop for i = 3 (vertex c), the matrix
is  
4 3 2 8 12 ∞
 3
 2 1 5 11 ∞  
 2 1 2 6 10 ∞ 
 
.
 8 5 6 10 2 6 

 
 12 11 10 2 20 3 
∞ ∞ ∞ 6 3 ∞
After completion of the main loop for i = 4 (vertex d), the matrix
is  
4 3 2 8 10 14
 3 2 1 5 7 11 
 
 2 1 2 6 8 12 
 
.
 8 5 6 10 2 6 

 
 10 7 8 2 4 3 
14 11 12 6 3 12
Shortest Path Problems 19
Floyd’s Algorithm

After completion of the main loop for i = 5 (vertex e), the matrix
is (boxed values are those that were updated)
 
4 3 2 8 10 13
 3 2 1 5 7 10 
 
 2 1 2 6 8 11 
 
 .
 8 5 6 4 2 5 
 
 10 7 8 2 4 3 
13 10 11 5 3 6

In this problem, there is no change after the final iteration with

i = 6 (vertex f ). Therefore this matrix represents the distances
between all pairs of vertices.

Shortest Path Problems 20