DATA STRUCTURES
& ALGORITHMS
Lecture 7: GRAPHS – part 2
Lecturer: Dr. Nguyen Hai Minh
OUTLINE
o Other applications of Graphs
n Shortest Path
n Circuits
n Difficult Problems
5/20/24 nhminh @ FIT 2
SHORTEST PATH
Dijkstra’s Algorithm
5/20/24 nhminh @ FIT 3
Shortest Paths
o Many problems can be modeled using graphs
with weights assigned to their edges:
n Airline flight problems
n Computer networks problems
n GPS navigation systems
5/20/24 nhminh @ FIT 4
Airline Flight Problems
o Vertices: cities
o Edges: flights
o Weights of
edges depend
on the problem.
n Distance
between cities
n Flight fare
n Flight time
n …
5/20/24 nhminh @ FIT 5
Computer Networks Problems
o Vertices: computers
o Edges: lines between
computers
o Weights:
n Communication costs
(e.g., monthly cost of
leasing a telephone
line)
n Response times of the
computers over these
lines
n Distances between
computers
5/20/24 6
Shortest Paths
o The input to the shortest-paths problem is a
weighted, directed graph 𝐺 = (𝑉, 𝐸), with a weight
function 𝑤: 𝐸àℝ mapping each edges to real-
valued weights.
o We define the shortest-path weight 𝜹 𝒖, 𝒗 from 𝑢
to 𝑣 by
𝒑
𝜹 𝒖, 𝒗 = &𝐦𝐢𝐧 𝒘 𝒑 : 𝒖 → 𝒗
if there is a path from 𝒖 to 𝒗
∞ otherwise
where
𝑤 𝑝 = ∑%"#$ 𝑤(𝑣"&$ , 𝑣" ) is the weight of path 𝑝 = 𝑣' , 𝑣$ , … , 𝑣%
5/20/24 nhminh @ FIT 7
Shortest Paths – Variants
o Single-source shortest paths problem
o Single-destination shortest paths problem
o Single-pair shortest paths problem
o All-pairs shortest paths problem
5/20/24 nhminh @ FIT 8
Shortest Paths – Negative-weight
o Negative-weight edges
Shortest cost
-4
a b path
4
3 6 sàa 3
sàb -1
s 5
c d 8
g sàc 5
-3
sàd 11
2 3 7 sàe -∞
e f sàf -∞
-6
sàg -∞
Negative cycles
5/20/24 nhminh @ FIT 9
Shortest Paths
o Cycles:
n A shortest path cannot contain a cycle
o Representing shortest paths: each vertex v
in the graph G has:
n A predecessor 𝒗. 𝝅 that is another vertex or NIL
n A shortest-path estimate 𝒗. 𝒅 which is an upper
bound on the weight of a shortest path from
source s to v
5/20/24 nhminh @ FIT 10
Shortest Paths
o Dijkstra’s shortest-path algorithm
n Determine the shortest path between a given
vertex and all other vertices (Single-source
shortest paths)
n Assume that weight of edges ≥ 0
n The directed graph G is stored in the
adjacency-list representation.
5/20/24 nhminh @ FIT 11
Dijkstra’s Algorithm Idea
o We maintain a set of vertices S whose final shortest path
lengths have already been determined
n In each time we consider not yet discovered vertices in the graph,
and all edges going from a discovered vertex (u) to an
undiscovered vertex (v).
n We choose an undiscovered vertex with an edge from u to v, that
gives the shortest path length.
n The length from u to v for each vertex v, is given by the length of u,
plus the weight between u and v.
o In the initialization step:
n We include source node S in the set of discovered
nodes and set its length to 0.
n All other lengths are initially infinity.
o Then we keep expanding set S of discovered nodes in a
greedy manner.
5/20/24 nhminh @ FIT 12
Dijkstra’s Algorithm
Update the min-priority
queue
5/20/24 nhminh @ FIT 13
Dijkstra’s Algorithm – Example
o A weighted directed graph and its adjacency
list
2
8
A B C A B8 D9 E4
1 B C1
4
3 C B2 D3
9 2 1 D C2 E7
E C1
D E
7
5/20/24 nhminh @ FIT 14
Dijkstra’s Algorithm – Example
Step
Init ∅
1
2
3
4
5 ∅
5/20/24 nhminh @ FIT 15
Dijkstra’s Algorithm – Example
o Init the distances and predecessors from A to all v
in G.
(0, NIL) (∞, NIL) (∞, NIL)
2
8
A B C
1
4
3
9 2 1
D E
7
(∞, NIL) (∞, NIL)
5/20/24 nhminh @ FIT 16
Dijkstra’s Algorithm – Example
(0, NIL) (8, A) (∞, NIL)
2
8
A B C
1
4
3
9 2 1
D E
7
(9, A) (4, A)
5/20/24 nhminh @ FIT 17
Dijkstra’s Algorithm – Example
(0, NIL) (8, A) (5, E)
2
8
A B C
1
4
3
9 2 1
D E
7
(9, A) (4, A)
5/20/24 nhminh @ FIT 18
Dijkstra’s Algorithm – Example
(0, NIL) (7, C) (5, E)
2
8
A B C
1
4
3
9 2 1
D E
7
(8, C) (4, A)
5/20/24 nhminh @ FIT 19
Dijkstra’s Algorithm – Example
(0, NIL) (7, C) (5, E)
2
8
A B C
1
4
3
9 2 1
D E
7
(8, C) (4, A)
5/20/24 nhminh @ FIT 20
Dijkstra’s Algorithm – Example
(0, NIL) (7, C) (5, E)
2
8
A B C
1
4
3
9 2 1
D E
7
(8, C) (4, A)
5/20/24 nhminh @ FIT 21
Dijkstra’s Algorithm – Example
(0, NIL) (7, C) (5, E)
2
8
A B C
1
4
3
9 2 1
D E
7
(8, C) (4, A)
5/20/24 nhminh @ FIT 22
Dijkstra’s Algorithm – Analysis
o We run through each node once.
o For each node we look into its adjacency list.
à (|𝑉| + |𝐸|) number of operations.
o However, each operation takes time since we need to
find the minimum among all possible edges.
à Use a priority queue with each minimum taking
𝑂(log ! |𝑉|) time.
o As a consequence, we have
𝑂((|𝑉| + |𝐸|) log ! |𝑉|) complexity.
5/20/24 nhminh @ FIT 23
Dijkstra’s Algorithm – Analysis
o We can improve this complexity to 𝑂(|𝐸| +
|𝑉| log ! |𝑉|) just like in Prim’s algorithm; i.e.,
implement the min-priority queue using
Fibonacci Heap.
5/20/24 nhminh @ FIT 24
Dijkstra’s Algorithm – Negative Edges
o Dijkstra’s algorithm fails when the graph has
negative weight.
5/20/24 nhminh @ FIT 25
CIRCUITS
Eurler Circuit
Hamilton Circuit
5/20/24 nhminh @ FIT 26
CIRCUITS
o A circuit is simply another name for a type of
cycle that is common in some problems.
n Recall: a cycle in a graph is a path that begins and
ends at the same vertex.
o Typical circuits either visit every vertex once or
visit every edge once.
5/20/24 nhminh @ FIT 27
CIRCUITS – The Bridge Problem
o The first application of graphs (early 1700s) by
Euler:
n Two islands in a river are joined to each other and
to the river banks by several bridges
n The bridges à edges in multigraph
n The land masses à vertices
n The problem asked whether you can begin at a
vertex v, pass through every edge exactly once,
and terminate at v.
5/20/24 nhminh @ FIT 28
CIRCUITS – The Bridge Problem
o No solution exists for this particular
configuration of edges and vertices.
5/20/24 nhminh @ FIT 29
Euler Circuits
o Euler circuit: path that begins at a vertex v,
passes through every edge in the graph exactly
once, and terminates at v.
n Consider a simple undirected graph rather than a
multigraph.
n Euler circuit exists if and only if each vertex touches
an even number of edges (or has an even degree).
5/20/24 nhminh @ FIT 30
Euler Circuits – Example
o Pencil and Paper drawings:
n Drawing without lifting your pencil or redrawing a
line, ending at your starting point.
No solution Has solution
5/20/24 nhminh @ FIT 31
Euler Circuits – Example
o Graphs based on previous example
deg = 3
No solution Has solution
5/20/24 nhminh @ FIT 32
Euler Circuits – Algorithm
o In case the Euler Circuit exists, we can find it
by a strategy using DFS that marks edges
instead of vertices as they are traversed.
n You will find a cycle.
n Then, find the first vertex along the cycle that
touches an unvisited edge.
n Loop until there is no unvisited edge.
5/20/24 nhminh @ FIT 33
SOME DIFFICULT
PROBLEMS
• The travelling salesperson problem
• The three utilities problem
• The four-color problem
5/20/24 nhminh @ FIT 34
The travelling salesperson problem
o A Hamilton circuit is a path that begins at a vertex v,
passes through every vertex in the graph exactly once, and
terminates at v.
à Determine whether a graph contains a Hamilton circuit is difficult!
o The TSP is a variation of this problem:
n Involves a weighted graph that represent a roadmap.
n Each edge has a cost.
à The salesperson must visit every city exactly once and return to the
original city with the least cost.
à Solving this problem is not easy!
5/20/24 nhminh @ FIT 35
The three utilities problem
o Is it possible to connect each house to each utility with
edges that do not cross one another?
NO!
Because it is not a
planar graph!
o Generation: Determine whether a given graph is planar?
n Design an electronic circuit so that the connections do not cross
5/20/24 nhminh @ FIT 36
The four-color problem
o Given a planar graph, can you color the
vertices so that no adjacent vertices have the
same color, if you use at most four colors?
à The answer is YES, but it is difficult to prove.
à In fact, this problem was posed more than a century
before it was solved in the 1970s with the use of a
computer.
5/20/24 nhminh @ FIT 37
The four-color problem – Example
o Use 3 colors to color the following map
b
a
c
i e h
g d
f
5/20/24 nhminh @ FIT 38
The four-color problem – Example
o Use 3 colors to color the following map
b
a
c
i e h
g d
f
5/20/24 nhminh @ FIT 39
What’s Next?
o After today:
n Read Textbook 1: Chapter 20, 21, 22
n Read Textbook 2: Chapter 20
5/20/24 nhminh @ FIT 40
5/20/24 nhminh @ FIT 41
