INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 9 – Graph algorithms II
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R
Aims of this lecture
• The lecture introduces two graph algorithms
– The shortest distances between one vertex to all the other
vertices in a graph
– The shortest distances between all pairs of vertices in a graph
2
CRICOS No. 00213J
a university for the worldreal R
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 8.4 and 9.3.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein,
Introduction to Algorithms, third edition, 2009. Chapters 24 and 25.
3
CRICOS No. 00213J
a university for the worldreal R
The shortest path problem
• The shortest path between two given vertices in a weighted
graph is the path that has minimal sum of its edge weights.
– For example, the shortest path from vertex A to vertex B is
AECB, rather than AB.
A B C
D E
8 1
2
9
7
4 3
2 1
The shortest path from vertex A to vertex B
4
CRICOS No. 00213J
a university for the worldreal R
The shortest path problem
• Although the term “shortest” is used, the weights could be a
measure other than distance, such as airfare.
• Consider a map of airline routes. A weighted directed graph
can represent this map: the vertices are cities, the edges
indicate existing flights between the cities, and weights
represent the airfares.
A B C
D E
8 1
2
9
7
4 3
2 1
5
CRICOS No. 00213J
a university for the worldreal R
Shortest path algorithms
• A* Algorithm – find the shortest path/distance between two
vertices (an intelligent search algorithm, beyond this unit).
• Dijkstra’s algorithm – find the shortest path/distance
between a vertex to all the other vertices in a graph.
• Floyd’s algorithm – find the shortest path/distance between
every pair of vertices in a graph.
6
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
• An algorithm that finds the shortest path/distance between a vertex
and all other vertices in a weighted graph.
• It was conceived by computer scientist Edsger W. Dijkstra in 1956.
7
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
• First, the algorithm finds the shortest distance from the source
vertex to a vertex nearest to it. Then, the algorithm finds the shortest
distance from the source vertex to a vertex second nearest to it, and
so on.
8
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
ALGORITHM Dijkstra (G, u)
// Input: A, which is the matrix representation of G;
// Output: W, which is an array containing the shortest path lengths
// between vertex u and all the other vertices in graph G(V, E);
//assume that vertices are represented by their corresponding row/column number
S ← {u}
N ←|V|
for j = 0 to N-1 do
W[j] = A[u][j]
for i = 2 to N do
find the smallest W[v] such that v is not in S;
S ← S + {v}
for all vertices x not in S do
if W[x] > W[v] + A[v][x]
W[x] = W[v] + A[v][x].
return W
9
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
A B C
D E
8 1
2
9
7
4 3
2 1
∞ 8 ∞ 9 4
∞ ∞ 1 ∞ ∞
∞ 2 ∞ 3 ∞
∞ ∞ 2 ∞ 7
∞ ∞ 1 ∞ ∞
A B C D E
A
B
C
D
E
The adjacency matrix representation:
10
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
Step v S W[0] W[1] W[2] W[3] W[4]
1 – {A} ∞ 8 ∞ 9 4
A B C D E
Initially, S contains vertex A, and W is the row of the graph’s
adjacency matrix corresponding to A (the 1st row).
11
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
A C
E
4 1
∞
Step v S W[0] W[1] W[2] W[3] W[4]
1 – {A} ∞ 8 ∞ 9 4
2 E {A,E} ∞ 8 5 9 4
A B C D E
W[4] is the smallest of all vertices not in S.
Thus, v = E, and add E to S.
For vertices not in S, that is, B, C and D,
check if it is shorter to go from A to E and
then along an edge to them instead of
directly from A to them.
– For vertices B and D, it is not shorter.
– For vertex C, however, it is shorter.
Therefore, W[2] is replaced by the
shorter distance.
12
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
A C
E
4 1
B8 2
Step v S W[0] W[1] W[2] W[3] W[4]
1 – {A} ∞ 8 ∞ 9 4
2 E {A,E} ∞ 8 5 9 4
3 C {A,E,C} ∞ 7 5 8 4
A B C D E
W[2] is the smallest of all vertices not in
S. Thus, v = C, and add C to S.
For vertices not in S, that is, B and D,
check if it is shorter to go from A to C and
then along an edge to them than the
current shortest paths found so far.
– For both vertices B and D, it is
shorter. Therefore, W[1] and W[3] are
replaced by the shorter distances.
A C
D E
9 4 3 1
13
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
Step v S W[0] W[1] W[2] W[3] W[4]
1 – {A} ∞ 8 ∞ 9 4
2 E {A,E} ∞ 8 5 9 4
3 C {A,E,C} ∞ 7 5 8 4
4 B {A,E,C,B} ∞ 7 5 8 4
A B C D E
W[1] is the smallest of all vertices not in S.
Thus, v = B, and add B to S.
For vertex D, which is the only vertex not in
S, check if it is shorter to go from A to B and
then along an edge to it than the shortest
found so far.
– It is not shorter. Therefore, leave W[3]
as it is.
14
CRICOS No. 00213J
a university for the worldreal R
Dijkstra’s algorithm
Step v S W[0] W[1] W[2] W[3] W[4]
1 – {A} ∞ 8 ∞ 9 4
2 E {A,E} ∞ 8 5 9 4
3 C {A,E,C} ∞ 7 5 8 4
4 B {A,E,C,B} ∞ 7 5 8 4
5 D {A,E,C,B,D} ∞ 7 5 8 4
A B C D E
Now, the only vertex not in S is D. So add it to S and terminates.
15
CRICOS No. 00213J
a university for the worldreal R
Efficiency of Dijkstra’s algorithm
• The time efficiency of the algorithm presented in this lecture is O(n3),
where n = |V|.
• However, if W is implemented as a priority queue, the time efficiency
will be O(n2), where n = |V|. (Levitin, p363)
16
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
• An algorithm that finds the shortest paths/distances from each
vertex to all other vertices in a weighted graph.
• It was invited by Robert Floyd in 1962.
17
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
• The basic idea behind the Floyd’s algorithm is to gradually build up
all the possible paths/distances from vertex i and vertex j to find the
shortest path/distance between vertices from vertex i to vertex j.
18
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
• Floyd’s algorithm computes the distance matrix of a weighted graph
with n vertices, D, through a series of n×n matrices:
D(1), … , D(k), … , D(n)
• dij(k) in the ith row and the jth column of matrix D(k) (i, j, k = 1, 2, … , n)
is equal to the length of the shortest path among all paths from the
ith vertex to the jth vertex with each intermediate vertex, if any,
numbered not higher than k.
• The recurrence formula:
19
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
20
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
∞ 8 ∞ 9 4
∞ ∞ 1 ∞ ∞
∞ 2 ∞ 3 ∞
∞ ∞ 2 ∞ 7
∞ ∞ 1 ∞ ∞
A B C D E
A
B
C
D
E
21
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
∞ 8 ∞ 9 4
∞ ∞ 1 ∞ ∞
∞ 2 ∞ 3 ∞
∞ ∞ 2 ∞ 7
∞ ∞ 1 ∞ ∞
A B C D E
A
B
C
D
E
22
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
∞ 8 9 9 4
∞ ∞ 1 ∞ ∞
∞ 2 3 3 ∞
∞ ∞ 2 ∞ 7
∞ ∞ 1 ∞ ∞
A B C D E
A
B
C
D
E
23
CRICOS No. 00213J
a university for the worldreal R
Floyd’s Algorithm
∞ 8 9 9 4
∞ 3 1 4 ∞
∞ 2 3 3 ∞
∞ 4 2 5 7
∞ 3 1 4 ∞
A B C D E
A
B
C
D
E
24
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
∞ 8 9 9 4
∞ 3 1 4 11
∞ 2 3 3 10
∞ 4 2 5 7
∞ 3 1 4 11
A B C D E
A
B
C
D
E
25
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
∞ 7 5 8 4
∞ 3 1 4 11
∞ 2 3 3 10
∞ 4 2 5 7
∞ 3 1 4 11
A B C D E
A
B
C
D
E
26
CRICOS No. 00213J
a university for the worldreal R
Floyd’s algorithm
∞ 7 5 8 4
∞ 3 1 4 11
∞ 2 3 3 10
∞ 4 2 5 7
∞ 3 1 4 11
A B C D E
A
B
C
D
E
dist
A B C
D E
8 1
2
9
7
4 3
2 1
27
CRICOS No. 00213J
a university for the worldreal R
Efficiency of Floyd’s algorithm
• Time efficiency
– O(n3), where n = |V|
28
CAB301 Algorithms and Complexity��Lecture 9 – Graph algorithms II
Aims of this lecture
References
The shortest path problem
The shortest path problem
Shortest path algorithms
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Efficiency of Dijkstra’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s Algorithm
Floyd’s algorithm
Floyd’s algorithm
Floyd’s algorithm
Efficiency of Floyd’s algorithm