8 8 8

>>

Week 5: Graph Algorithms

61 61 61 61
-4Week 5 -4 -4 -4
31 Things You Should Know
Nerdy 31 31 31
62Graphs
Directed 62 62 62
91 (Digraphs)
Directed Graphs 91 91
28
Digraph Applications 28 28
Digraph Representation
Reachability
Transitive Closure
Exercise: Transitive Closure Matrix
Exercise: Transitive Closure
61 Digraph Traversal 61 61 61
-4 Example: Web Crawling -4 -4 -4
31
Weighted Graphs 31 31 31
62
Weighted Graphs 62 62 62
91
Exercise: Implementing a Route Finder 91 91
28
Weighted Graph Representation 28 28
Minimum Spanning Trees
Exercise: Minimising Wires in Circuits
Minimum Spanning Trees
Kruskal's Algorithm
Exercise: Kruskal's Algorithm
61 Prim's Algorithm 61 61 61
-4 Exercise: Prim's Algorithm -4 -4 -4
31
Sidetrack: Priority Queues 31 31 31
62
Other MST Algorithms 62 62 62
91
Shortest Path 91 91
Shortest Path 2 2 2
 8 8 8
Single-source Shortest Path (SSSP)
Edge Relaxation
Dijkstra's Algorithm
Exercise: Dijkstra's Algorithm
All-pair Shortest Path (APSP)
61 Floyd's Algorithm
61 61 61
-4 -4 -4 -4
31
Exercise: Floyd's Algorithm
Digraph Applications
31 31 31
62
PageRank
62 62 62
91
Exercise: Implementing Facebook
91 91
Network Flow
28 28 28
Exercise: Merchandise Distribution
Flow Networks
Augmenting Paths
Residual Network
Exercise: Augmenting Paths and Residual Networks
61 Edmonds-Karp Algorithm
61 61 61
-4 -4 -4 -4
31
Exercise: Edmonds-Karp Algorithm 31 31 31
62
Summary
62 62 62
91 91 91
28
COMP9024 24T1 ♢Dynamic Data Structures♢ [0/88] 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

∧ >>
61❖ Week 5 61 61 61
-4 -4 -4 -4
31 31 31 31
62 …
In This Lecture 62 62 62
91 91 91
28 28 28
Directed graphs, weighted graphs ([S] 19.1-19.3, 20-20.1)
More graph algorithms ([S] 20.2-20.4, 21-21.3, 22.1-22.2)

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [1/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Nerdy Things You61Should Know 61 61
-4 -4 -4 -4
31 31 31 31
6the
Consider 29 following scenario … 629 62 62
12 12 91
you're sitting8in a lab 8 28
you're looking at some code like '/^s?[0-9]{7}$/'
you want to ask a question about the code
61 but you're not sure how6to refer to the ^ char 61 61
1-
-4and you don't want to sound4 clueless -4 -4
31 31 31 31
62 62 62 62
Fear not! This
91is … How to speak #@*%$! 91 Ascii 91
28 28 28
From
blog.codinghorror.com/ascii-pronunciation-rules-for-programmers/

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [2/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Nerdy Things You61Should Know (cont) 61 61
-4 -4 -4 -4
31 31 31 31
Symbol62 Common Name 62
Silliest Name 62 62
91 91 91
& 28 28 28
*
"
61^ 61 61 61
-4 -4 -4 -4
@ 31 31 31 31
62 62 62 62
! 91 91 91
28 28 28
#
%

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [3/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Directed Graphs61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [4/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Directed Graphs6(Digraphs)
1 61 61
-4 -4 -4 -4
31 31 31 31
62 discussion of graphs:62
In our previous 62 62
91 91 91
28 a relationship between
an edge indicates 28two vertices 28
an edge indicates nothing more than a relationship

In many real-world applications of graphs:

61 edges are directional (6
v1→ w ≠ w → v) 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62have a weight (cost to go6from
edges 2 v → w) 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [5/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Directed Graphs6(Digraphs)
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
Example6digraph 62 representation:
29 and adjacency matrix 62 62
12 91 91
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
Undirectional ⇒ symmetric matrix
Directional ⇒ non-symmetric matrix

6Maximum #edges in a 6
digraph with V vertices: V 2 61 61
1- 1- -4 -4
43 43 31 31
1 6 1
29 ♢Dynamic Data Structures♢629
COMP9024 24T1 [6/88] 62
91
62
12 12 2
 8 8 8

<< ∧ >>
61❖ Directed Graphs6(Digraphs)
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 for digraphs …
Terminology 62 62 62
91 91 91
Directed path:2sequence
8 of n ≥ 2 vertices2v8
1 → v 2 → … → v n
2 8
where (vi,vi+1) ∈ edges(G) for all vi,vi+1 in sequence
if v1 = vn, we have a directed cycle
61 61 61 61
-
43
Reachability:
-
43 v if ∃ directed path v,…,w43
w is reachable from
- -4
16 16 16 31
29 29 29 62
12 12 12
8 8 8

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [7/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Digraph Applications 61 61 61
-4 -4 -4 -4
31 31 31 31
62application areas:
Potential 62 62 62
91 91 91
Domain
2 8 Vertex
2
Edge 8
28
Web web page hyperlink
scheduling task precedence
61 61 61 61
chess
-4 board position
-4 legal move -4 -4
31 31 31 31
science6 journal article 6citation 62 62
29 29 91
12
dynamic data 12
8 malloc'd object pointer
8 28
programs function function call
make file dependency
61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [8/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Digraph Applications 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
Problems62to solve on digraphs: 62 62 62
91 91 91
28 path from s to t? (transitive
is there a directed 28 closure) 28
what is the shortest path from s to t? (shortest path)
are all vertices mutually reachable? (strong connectivity)
61 how to organise a set of6tasks? (topological sort) 61 61
1-
-4which web pages are "important"? -4 -4
31 43 (PageRank) 31 31
6 16 62 62
how to2build a web crawler? (graph2
traversal)
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [9/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Digraph Representation 61 61 61
-4 -4 -4 -4
31 31 31 31
62of choices as for undirectional
Similar set 62 graphs: 62 62
91 91 91
28 (directed)
array of edges 28 28
vertex-indexed adjacency matrix (non-symmetric)
vertex-indexed adjacency lists
6V1vertices identified by 0 ..6V-1
1- 61 61
-4 43 -4 -4
31 16 31 31
62 29 62 62
91 12 91
28 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [10/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Reachability 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [11/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Transitive Closure 61 61 61
-4 -4 -4 -4
31 31 31 31
62 G it is potentially useful
Given a digraph 62 to know 62 62
91 91 91
28
is vertex t reachable from vertex s? 28 28
Example applications:
can I complete a schedule from the current state?
61 61referenced by any pointer?
is a malloc'd object being 61 61
-4 -4 -4 -4
3 1
Transitive
3 1 3 16 31
62closure: a -> b, b-> c then6a->
29 c
29 62
91 12 a set of places one can get
12to from a
28 closure (TC) gives you
Informally, transitive 8 8
starting place

How to compute transitive closure?

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [12/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Transitive Closure 61(cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 of implementing reachable()
One possibility 62 : 62 62
91 91 91
implement 2 it8via hasPath(G,s,t) (itself2implemented
8 28
by DFS or BFS algorithm)

feasible if reachable(G,s,t) is infrequent operation

What if we have an algorithm that frequently needs to check reachability?

61 61 61 61
Would
-4 be very convenient/efficient
-4 to have: -4 -4
31 31 31 31
62
reachable(G,s,t): 62 62 62
9
| return 1G.tc[s][t]
91
// transitive closure matrix
91
2 8 28 28
Of course, if V is very large, then this is not feasible.

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [13/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Transitive 61 Closure Matrix 61 61
-4 -4 -4 -4
31 31 31 31
62
Which reachable 62 graph?
s .. t exist in the following 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [14/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
6Transitive
1- closure of example
6 1-graph: 61 61
43 43 -4 -4
16 16 31 31
29 29 62 62
12 12 91
8 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [15/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Transitive 61 Closure Matrix (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62 a matrix of reachability
Goal: produce 62values 62 62
91 91 91
28then t is reachable from s28
if tc[s][t] is 1, 28
if tc[s][t] is 0, then t is not reachable from s

So, how to create this matrix?

61 61 61 61
Observation:
-4 -4 -4 -4
31 31 31 31
∀i,s,t ∈ 6 29 G):
vertices( 62 62 62
12G) and (i,t) ∈ edges(G) ⇒91tc[s][t]
(s,i) ∈ edges( 2 =1
91
28
8 8
tc[s][t]=1 if there is a path from s to t of length 2 (s→i→t)

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [16/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Transitive 61 Closure Matrix (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62
If we implement the above as: 62 62 62
91 91 91
make tc[][]2a8 copy of edges[][] 28 28
for all i∈vertices(G) do
for all s∈vertices(G) do
for all t∈vertices(G) do
if tc[s][i]=1 and tc[i][t]=1 then
61 6
tc[s][t]=1 1-
61 61
-4 43 -4 -4
31 end if 1 31 31
6end
29 for 62 62 62
end for1 91 91
end for
28 28 28
then we get an algorithm to convert edges into a tc

6This
1-
is known as Warshall's6algorithm
1- 61 61
43 43 -4 -4
COMP9024 1624T1 ♢Dynamic Data Structures♢
16 31 31
29
[17/88]
29 62 62
12 12 91
2
 8 8 8

<< ∧ >>
61❖ Exercise: Transitive 61 Closure Matrix (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62 …
How it works 62 62 62
91 91 91
After iteration21,8tc[s][t] is 1 if 28 28
either s→t exists or s→0→t exists

6After iteration 2, tc[s][t] is 1 if any of the following exist

1- s→t or s→0→t or s→1→t 61 61 61
43 -4 or s→0→1→t or s→1→0→t -4 -4
16 31 31 31
2
Etc. … so after V th 6 2 6 29 62
91the iteration, tc[s][t]91is 1 if 12
2 8
there is any directed 2
path in the graph from8 s to t 8

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [18/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Transitive 61 Closure 61 61
-4 -4 -4 -4
31 31 31 31
62
Trace Warshall's 62 graph:
algorithm on the following 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [19/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
611st iteration i=0: 61 61 61
tc-4[0]
31 [1] [2] [3]
-4
31
-4
31
-4
31
[0] 0 612 1 1 62 62 62
91 91 91
[1] 1 1 1 28 1 28 28
[2] 0 1 0 0
[3] 0 0 0 0
2 nd iteration i=1:
6 1tc- 61 61 61
4[0] [1] [2] [3] -4 -4 -4
31 31 31 31
[0] 1 61 1 1 62 62 62
29 91 91
[1] 1 1 1 12 1 28 28
8
[2] 1 1 1 1
[3] 0 0 0 0
3rd iteration i=2: unchanged
61 61 61 61
-
4th4
iteration i=3: unchanged
-4 -4 -4
3 16 31 31 31
29 62 62 62
12 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [20/88]
91
2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Transitive61 Closure (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Cost analysis: 62 62 62
91 91 91
28 V2 items (each item may
storage: additional
28be 1 bit) 28
computation of transitive closure: O(V3)
computation of reachable(): O(1) after having generated tc[][]
6Amortisation:
1- 6 1
would need many
6
calls to reachable() to1justify
61
43 - 43 -4 other costs -4
1 1 31 31
62 use DFS in each call to reachable()
Alternative: 62 62 62
91
Cost analysis: 91 91
28 28 28
storage: cost of queue and set during reachable
computation of reachable(): cost of DFS = O(V2) (for adjacency matrix)

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [21/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Digraph Traversal61 61 61
-4 -4 -4 -4
31 31 31 31
62
Same algorithms 62
as for undirected graphs: 62 62
91 91 91
depthFirst(v):28 28 28
1. mark v as visited
2. for each (v,w)∈edges(G) do
61 if w has not been visited
61then 61 61
-4 depthFirst(w) -4 -4 -4
31 31 31 31
62 62 62 62
91
breadth-first(v): 91 91
28 28 28
1. enqueue v
2. while queue not empty do
dequeue v
61 if v not already visited6then 61 61
-4 mark v as visited 1-4 -4 -4
3enqueue
1 31 to v
each vertex w adjacent 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [22/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Example: Web Crawling 61 61 61
-4 -4 -4 -4
31 31 31 31
62every page on the web 62
Goal: visit 62 62
91 91 91
28 search with "implicit"
Solution: breadth-first 28graph 28
webCrawl(startingURL):
| mark startingURL as alreadySeen
61|| enqueue(Q,startingURL)
while Q is not
61 do
empty
61 61
-| 4 | nextPage=dequeue(Q)-4 -4 -4
31 31 31 31
| | 6visit
2 nextPage 62 62 62
| | for91each hyperLink on nextPage91 do 91
| | | if2hyperLink
8 28 then
not alreadySeen 28
| | | mark hyperLink as alreadySeen
| | | enqueue(Q,hyperLink)
| | | end if
61|| |endend for
while
6 1- 61 61
-
43 43 -4 -4
1 1 31 31
6
visit scans 62
29page and collects e.g. keywords and links 62 62
12 91 91
2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [23/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graphs61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [24/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graphs61 61 61
-4 -4 -4 -4
31 31 31 31
62far have considered 62
Graphs so 62 62
91 91 91
28
edge = an association 28
between two vertices/nodes 28
may be a precedence in the association (directed)

Some applications require us to consider

61 61
a cost or weight of an association 61 61
-4 -4 -4 -4
31 by assigning values3to1 edges (e.g. positive reals)
modelled 31 31
62 62 62 62
91be used in both directed and
Weights can 91undirected graphs. 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [25/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graphs61(cont) 61 61
-4 -4 -4 -4
31 31 31 31
Example:62major airline flight routes 6in2Australia 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6Representation:
1- 6 1 6 1-
edge = direct flight;- weight = approx flying time (hours)
61
43 43 43 -4
16 16 16 31
29 ♢Dynamic Data Structures♢ 29 29 62
COMP9024 24T1 [26/88]
12 12 12
 8 8 8

<< ∧ >>
61❖ Weighted Graphs61(cont) 61 61
-4 -4 -4 -4
31 31 31 31
Weights6lead 62
29 to minimisation-type questions, e.g. 62 62
12 91 91
1. Cheapest way8to connect all vertices? 28 28
a.k.a. minimum spanning tree problem
assumes: edges are weighted and undirected
61 61 61 61
2. -Cheapest
4 way to get from A-4
to B? -4 -4
3 1
a.k.a6
shortest path problem
3 1 3 16 31
29 6 29 29 62
assumes: 1 12 or undirected
edge weights positive, directed 12
28 8 8

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [27/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Implementing 61 a Route Finder61 61
-4 -4 -4 -4
31 31 31 31
62 a street map as a graph
If we represent 62 62 62
91 91 91
28vertices?
what are the 28 28
what are the edges?
are edges directional?
61 what are the weights? 61 61 61
-4are the weights fixed? -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [28/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graph6Representation
1 61 61
-4 -4 -4 -4
31 31 31 31
Weights6can
29easily be added to: 629 62 62
12 12 91
adjacency matrix
8 representation (0/1 → 8int or float) 28
adjacency lists representation (add int/float to list node)

Both representations work whether edges are directed or not.

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [29/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graph6Representation
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62matrix representation with
Adjacency 62weights: 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
Note: need distinguished value to indicate "no edge".

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [30/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graph6Representation
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62lists representation with6weights:
Adjacency 2 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

Note: if undirected, each edge appears twice with same weight

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [31/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graph6Representation
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Sample adjacency 62 in C requires minimal6changes
matrix implementation 2 to previous 62
Graph ADT:91 91 91
28 28 28
WGraph.h
// edges are pairs of vertices (end-points) plus positive weight
typedef struct Edge {
61 Vertex v; 61 61 61
-4 Vertex w; -4 -4 -4
31 31 31 31
int6 weight; 62 62 62
2
} Edge; 91 91 91
28 28 28
// returns weight, or 0 if vertices not adjacent
int adjacent(Graph, Vertex, Vertex);

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [32/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Weighted Graph6Representation
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
WGraph.c62 62 62 62
91 91 91
28 GraphRep {
typedef struct 28 28
int **edges; // adjacency matrix storing positive weights
// 0 if nodes not adjacent
int nV; // #vertices
int nE; // #edges
61} GraphRep; 61 61 61
-43 -4 -4 -4
16 31 31 31
29 62 62 62
12
void insertEdge(Graph g, Edge e)9{1 91
8 NULL && validV(g,e.v)28&& validV(g,e.w)); 28
assert(g !=
if (g->edges[e.v][e.w] == 0) { // edge e not in graph
g->edges[e.v][e.w] = e.weight;
g->nE++;
61 } 61 61 61
}-4 -4 -4 -4
31 31 31 31
62
int adjacent(Graph 62 Vertex w) {
g, Vertex v, 62 62
91 != NULL && validV(g,v)
assert(g
91 && validV(g,w)); 91
2 2 2
 8 8 8
return g->edges[v][w];
}

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [33/88] 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Minimum Spanning
61 Trees 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [34/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Minimising 61 Wires in Circuits61 61
-4 -4 -4 -4
31 31 31 31
62circuit designs often need6to
Electronic 2 make the pins of several6components
29 62
9
electrically equivalent
12 9
by wiring them together.
12 12
8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
To interconnect a set of n pins we can use an arrangement of n-1 wires each
connecting two pins.

6What
1-
kind of algorithm would …
61 61 61
4help -4 with the least amount of-wire?
43 -4
31 us find the arrangement31 16 31
62 62 29 62
91 91 12
28 Data Structures♢
COMP9024 24T1 ♢Dynamic [35/88]28 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Minimum Spanning 61 Trees 61 61
-4 -4 -4 -4
31 31 31 31
62Spanning tree ST of graph62G=(V,E)
Reminder: 62 62
91 91 91
spanning = 2
all8vertices, tree = no cycles28 28
ST is a subgraph of G (G'=(V,E') where E' ⊆ E)
ST is connected and acyclic
6Minimum
1- 61of graph G
spanning tree MST 61 61
4MST -4 -4 -4
31 is a spanning tree of G 31 31 31
62 62 62 62
91 weights is no larger than
sum of edge 91any other ST 91
28 28 28
Applications: Computer networks, Electrical grids, Transportation networks …

Problem: how to (efficiently) find MST for graph G?

6NB:
1- MST may not be unique (e.g.6all edges have same weight ⇒ every
1- 6 ST is MST)
1- 61
43 43 43 -4
1 24T1 ♢Dynamic Data Structures♢ 16 16 31
COMP90246 62
29 29
[36/88]
29
12 12 12
 8 8 8

<< ∧ >>
61❖ Minimum Spanning
61 Trees (cont) 61 61
-4 -4 -4 -4
31 31 31 31
Example:62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6An
1- MST … 61 61 61
43 -4 -4 -4
16 31 31 31
29 62 62 62
12 91 91
2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [37/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Minimum Spanning 61 Trees (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 solution:
Brute force 62 62 62
91 91 91
findMST(G):28 28 28
| Input graph G
| Output a minimum spanning tree of G
|
61|| bestCost=∞ 6 1- t of G do 61 61
-4 for all spanning trees43 -4 -4
| 3|1 if cost(t)<bestCost then
1 31 31
6
| | 2 bestTree=t 62 62 62
| | 9bestCost=cost(t)
12 91 91
| | end if 8
28 28
| end for
| return bestTree

6Example of generate-and-test
6 algorithm. 61 61
1- 1- -4 n-2 -4
4 31 because #spanning trees
Not useful
4 31 is potentially large (e.g. n31for a complete graph with n 31
vertices) 62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [38/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Minimum Spanning 61 Trees (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 assumption:
Simplifying 62 62 62
91 91 91
28 not directed (MST for digraphs
edges in G are 28 is harder) 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [39/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Kruskal's Algorithm 61 61 61
-4 -4 -4 -4
31 31 31 31
62 to computing MST for62graph G with V nodes: 62
One approach 62
91 91 91
28 MST
1. start with empty 28 28
2. consider edges in increasing weight order
add edge if it does not form a cycle in MST
613. repeat until V-1 edges are 61 added 61 61
- 4 - 43 -4 -4
3operations:
Critical
16 16 31 31
29 edges in weight order 29 62 62
iterating over
12 12 91
8 in a graph
checking for cycles 8 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [40/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Kruskal's Algorithm 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62trace of Kruskal's algorithm:
Execution 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [41/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Kruskal's 61Algorithm 61 61
-4 -4 -4 -4
31 31 31 31
Show how62Kruskal's algorithm produces
62 an MST on: 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [42/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
6After 3rd iteration: 61 61 61
1- -4 -4 -4
43 31 31 31
16 62 62 62
29 91 91
12 28 28
8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
After 6th6iteration:
2 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
After 7th iteration:

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

After 8th iteration (V-1=8 edges added):

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62
COMP9024 24T1 ♢Dynamic Data Structures♢ [43/88] 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Kruskal's
61Algorithm (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Pseudocode: 62 62 62
91 91 91
28
KruskalMST(G): 28 28
| Input graph G with n nodes
| Output a minimum spanning tree of G
|
61|| MST=empty graph
6 1- 61 61
-4 sort edges(G) by weight 43 do -4 -4
| 3 for
1 each e∈sortedEdgeList 1 31 31
| | MST6 29 = MST ∪ {e} 62 62 62
| | if MST 12 has a cyle then 912 91
28
| | MST 8= MST \ {e} 8
| | end if
| | if MST has n-1 edges then
| | return MST
61| | end if 61 61 61
|-4 end for -4 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [44/88] 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Kruskal's 61Algorithm (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 complexity analysis … 62
Rough time 62 62
91 91 91
28list is O(E·log E)
sorting edge 28 28
at least V iterations over sorted edges
on each iteration …
61 cost edge is O(1)
getting next lowest6 61 61
-4 1- -4 -4
3 checking whether 4
adding it
3 forms a cycle: cost = ?? 3 31
16 16 16 62
29for cycle checking:
Possibilities 29 29
12 12 12
use DFS … too 8 expensive? 8 8
could use Union-Find data structure (see Sedgewick Ch.1)

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [45/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Prim's Algorithm61 61 61
-4 -4 -4 -4
31 31 31 31
Another6approach
29 to computing MST62for graph G=(V,E): 62 62
12 91 91
8 vertex v and empty MST28
1. start from any 28
2. choose edge not already in MST to add to MST
must be incident on a vertex s already connected to v in MST
61 must be incident on6a vertex t not already connected
6 to v in MST 61
-4 1- 1- -4
43of all such edges
3 must have minimal weight 43 31
16 16 16 62
3. repeat2until MST covers all vertices
2 29
91 91 12
28
Critical operations: 28 8
checking for vertex being connected in a graph
finding min weight edge in a set of edges

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [46/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Prim's Algorithm6(cont) 1 61 61
-4 -4 -4 -4
31 31 31 31
62trace of Prim's algorithm6(starting
Execution 2 at s=0): 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [47/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Prim's Algorithm
61 61 61
-4 -4 -4 -4
31 31 31 31
Show how62Prim's algorithm produces
62an MST on: 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6Start
1- from vertex 0 61 61 61
43 -4 -4 -4
16 31 31 31
29 ♢Dynamic Data Structures♢629
COMP9024 24T1 [48/88]
62
91
62
12 12 2
 8 8 8

<< ∧ >>
6After 1st iteration: 61 61 61
1- -4 -4 -4
43 31 31 31
16 62 62 62
29 91 91
12 28 28
8
After 2nd iteration:

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2
After 3rd iteration:
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
After 4th iteration:

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6After 61 covered):
1- 8th iteration (all vertices 61 61
43 -4 -4 -4
16 31 31 31
29 62 62 62
12 91 91
2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [49/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Prim's Algorithm
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Pseudocode: 62 62 62
91 91 91
PrimMST(G):28 28 28
| Input graph G with n nodes
| Output a minimum spanning tree of G
|
61|| MST=empty graph
6 1 6 1- 61
-4 usedV={0} -4 43 -4
| 3 unusedE=edges(g)
1 3 1 1 31
| while6 29|usedV|<n do 6 29 62 62
| | find1 e=(s,t,w)∈unusedE such 1 that { 91
| |
28
s∈usedV, t∉usedV and w is 8
2 min weight of all such2edges
8
| | }
| | MST = MST ∪ {e}
| | usedV = usedV ∪ {t}
61| | unusedE = unusedE 61\ {e} 61 61
|-4 end while -4 -4 -4
| 3 1
return MST 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
Critical operation: finding best edge

COMP9024 24T1 ♢Dynamic Data Structures♢ [50/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Prim's Algorithm
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 complexity analysis … 62
Rough time 62 62
91 91 91
V iterations2of
8 outer loop 28 28
in each iteration …
find min edge with set of edges is O(E) ⇒ O(V·E) overall
61 find min edge with priority
6 queue is O(log E) ⇒ 6
O(V·log E) overall 61
-4 1- 1- -4
31 43 43 31
62 16 16 62
91 29 29
28 12 12
8 8

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [51/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Sidetrack: Priority 61Queues 61 61
-4 -4 -4 -4
31 31 31 31
62
Some applications of queues require62 62 62
91 91 91
28 in order of "priority" 28
items processed 28
rather than in order of entry (FIFO — first in, first out)

Priority Queues (PQueues) provide this via:

61 61 with an associated priority
join: insert item into PQueue 61 (replacing enqueue) 61
-4 -4 -4 -4
31 remove item with highest
leave: 31 priority (replacing dequeue)31 31
62 62 62 62
91 for naive implementation
Time complexity 91 of a PQueue containing9N1items …
28 28 28
O(1) for join O(N) for leave

Most efficient implementation ("heap") …

O(log N) for join, leave
61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [52/88]
31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Other MST Algorithms 61 61 61
-4 -4 -4 -4
31 31 31 31
62algorithm … complexity O(E·log
Boruvka's 62 V) 62 62
91 91 91
28 algorithm
the oldest MST 28 28
start with V separate components
join components using min cost links
61 continue until only a single
6 component 61 61
-4 1- -4 -4
Karger,
43 O(E)
31Klein, and Tarjan … complexity 31 31
62 16 62 62
based on 29
91Boruvka, but non-deterministic 91
2 12 28
8 subset of edges to consider
randomly selects 8
for the keen, here's the paper describing the algorithm

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [53/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Shortest Path 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [54/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Shortest Path 61 61 61
-4 -4 -4 -4
31 31 31 31
62
Path = sequence of edges in graph G62p = (v0,v1), (v1,v2), …, (vm-1,vm) 62 62
91 91 91
28of edge weights along path
cost(path) = sum 28 28
Shortest path between vertices s and t

a simple path p(s,t) where s = first(p), t = last(p)

61 61 61 61
-4no other simple path q(s,t)-has
4 cost(q) < cost(p) -4 -4
31 31 31 31
62 weighted digraph, no 6negative
Assumptions: 2 weights. 62 62
91 91 91
2 2 2
Finding shortest path between two given nodes known as source-target8SP problem
8 8
Variations: single-source SP, all-pairs SP

6Applications:
1-
navigation, routing
6 1-
in data networks, …6
1- 61
43 43 43 -4
COMP90241624T1 ♢Dynamic Data Structures♢
16 16 31
29
[55/88]
29 29 62
12 12 12
 8 8 8

<< ∧ >>
61❖ Single-source Shortest 61 Path (SSSP) 61 61
-4 -4 -4 -4
31 31 31 31
62
Given: weighted 62 s
digraph G, source vertex 62 62
91 91 91
28paths from s to all other vertices
Result: shortest 28 28
dist[] V-indexed array of cost of shortest path from s
pred[] V-indexed array of predecessor in shortest path from s
61 61 61 61
Example:
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2
COMP9024 24T1 ♢Dynamic Data Structures♢ [56/88] 2 2
 8 8 8

<< ∧ >>
61❖ Edge Relaxation 61 61 61
-4 -4 -4 -4
31 31 31 31
Assume:6dist[]
29 and pred[] as above 62(but containing data for shortest
62paths discovered so far) 62
12 91 91
dist[v] is length 28 s to v
8of shortest known path from 28
dist[w] is length of shortest known path from s to w

Relaxation updates data for w if we find a shorter path from s to w:

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
Relaxation
-4 along edge e=(v,w,weight):
-4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
if dist[v]+weight < dist[w] then
update dist[w]:=dist[v]+weight and pred[w]:=v

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [57/88] 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Dijkstra's Algorithm 61 61 61
-4 -4 -4 -4
31 31 31 31
62 to solving single-source
One approach 62 shortest path problem …62 62
91 91 91
28 pred[] and
Data: G, s, dist[], 28 28
vSet: set of vertices whose shortest path from s is unknown

Algorithm:
61 61 61 61
-4
dist[] -shortest
43 path from s -4 -4
31 // array of cost of
16shortest path from s 31 31
pred[]6 // array of predecessor in 62 62
29 29 91
12
dijkstraSSSP(G,source):
12 28
8 8
| Input graph G, source node
|
| initialise dist[] to all ∞, except dist[source]=0
61|| initialise
vSet=all
pred[] to all -1
vertices 61G
of 61 61
- while vSet≠∅ do -4
| 43
-4 -4
1 31 31 31
| | 6find
29 s∈vSet with minimum62 dist[s] 62 62
| | for 1each (s,t,w)∈edges(G)91 do 91
2 2 2
 8 8 8
| | relax along (s,t,w)
| | end for
| | vSet=vSet\{s}
61 | end while 6 61 61
-4 1- -4 -4
3 43 31 31
1624T1 ♢Dynamic Data Structures♢
COMP9024 16[58/88] 62 62
29 29 91
12 12 28
8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Dijkstra's 61 Algorithm 61 61
-4 -4 -4 -4
31 31 31 31
Show how62Dijkstra's algorithm runs6on2 (source node = 0): 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 [0] [1] [2] [3] [4] [5] -4 -4 -4
3
dist 1
06 ∞ ∞ ∞ ∞ ∞
31 31 31
2–9 62 62 62
pred – 1–2 – – – 91 91
2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [59/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4 [0] [1] [2] [3] [4] [5] -4 -4 -4
3
dist 106 ∞ ∞ ∞
31 31 31
∞ ∞ 62 62 62
29 91 91
pred – – 1– – – –
28 28 28
dist 0 14 9 7 ∞ ∞
pred – 0 0 0 – –
6dist
1- 0 14 9 7 61 61 61
43 ∞ 22 -4 -4 -4
pred 1
–6 0 0 0 – 3
31 31 31
29 62 62 62
12 91 91
dist 0 13 9 8 7 ∞ 12 28 28
pred – 2 0 0 – 2

dist 0 13 9 7 20 12
6pred
1- – 2 0 0 5
61
2
61 61
43 -4 -4 -4
16 31 31 31
dist 0 2
13 9 7 18 12 62 62 62
91 91 91
pred – 2 2 0
0 1 2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [60/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Dijkstra's 61 Algorithm (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Time complexity analysis … 62 62 62
91 91 91
28to be considered once ⇒ 2O(E)
Each edge needs 8 . 28
Outer loop has O(V) iterations.

6Implementing
1-
"find s∈vSet with minimum dist[s]"
61 61 61
4 - - -4
31all s∈vSet ⇒ cost = O(V)3⇒1overall cost = O(E + V )4=3O(V
1. try 4 2
16
2)
31
6
2. using a2PQueue
6 29 minimum 29 62
91 to implement extracting 12 12
2 8 overall cost to O(E + V·log
can improve 8 V) (for best-known implementation)
8

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [61/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ All-pair Shortest 6Path 1 (APSP) 61 61
-4 -4 -4 -4
31 31 31 31
62
Given: weighted digraph G 62 62 62
91 91 91
28paths between all pairs of2vertices
Result: shortest 8 28
dist[][] V×V-indexed matrix of cost of shortest path from vrow to vcol
path[][] V×V-indexed matrix of next node in shortest path from vrow to vcol
61 61 61 61
-4
Example: -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6e.g.,
1- 0 to 3, 1 to 0 61 61 61
43 -4 -4 -4
16 31 31 31
29 ♢Dynamic Data Structures♢629
COMP9024 24T1 [62/88]
62
91
62
12 12 28
8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Floyd's Algorithm61 61 61
-4 -4 -4 -4
31 31 31 31
62 to solving all-pair shortest
One approach 62 path problem… 62 62
91 91 91
28 path[][] Algorithm: 28
Data: G, dist[][], 28
dist[][] // array of cost of shortest path from s to t
path[][] // array of next node after s on shortest path from s to t

61floydAPSP(G): 61 61 61
-| 4 Input graph G -4 -4 -4
31 31 31 31
| 62 62 62 62
91 dist[s][t]=0 for each
| initialise 91 s=t 91
| 28 =w for each2(s,t,w)∈edges(G)
8 28
| =∞ otherwise
| initialise path[s][t]=t for each (s,t,w)∈edges(G)
| =-1 otherwise
61|| |forfor
all i∈vertices(G)
6 1
all s∈vertices(G)
do 6 1- 61
-4 -4 do 43 -4
| 3 31 do
|1 | for all t∈vertices(G) 16 31
6 6
| | |2 | if dist[s][i]+dist[i][t]
2 < dist[s][t] then2 62
| | | 9|1 91
dist[s][t]=dist[s][i]+dist[i][t] 91
2 2 2
 8 8 8
| | | | path[s][t]=path[s][i]
| | | | end if
| | | end for
61|| | end for
end for
6 1- 61 61
- 43 43 -4 -4
16 16 31 31
29 ♢Dynamic Data Structures♢ 29 62 62
COMP9024 24T1
12 [63/88]
12 91
8 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Floyd's 6Algorithm
1- 61 61
-4 43 -4 -4
31 16 31 31
Show how62Floyd's algorithm runs on: 29 62 62
91 12 91
28 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 [0] [1] [2] [3] [4] [5] path
dist -4 [0] [1] [2] [3] [4] [5] -4 -4
31 31 31 31
[0] 06 14 9 7 [0] 62 1 2 3 62 62
29 91 91
[1] 0 12 5 [1]
2 4
2
 8 8 8
[2] 4 0 3 [2] 1 5
[3] 10 0 15 [3] 2 5

61[4] 0 61 [4] 61 61
-4
[5] 2 0 -[5]
43 4 -4 -4
3 16 1 31 31
29 62 62 62
12 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [64/88]
91
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
After 1st iteration i=0: unchanged
-4 -4 -4 -4
31 31 31 31
6
After 2nd 2
iteration i=1:
62 62 62
9 12 91 91
8 28 28
dist [0] [1] [2] [3] [4] [5] path [0] [1] [2] [3] [4] [5]
[0] 0 14 9 7 19 ∞ [0] – 1 2 3 1 –
[1] ∞ 0 ∞ ∞ 5 ∞ [1] – – – – 4 –
61 61 [2] – 1 – – 1
651 61
-4 ∞ 4
[2] 0 ∞ 9 3 -4 -4 -4
31 31 – – 2
[3] – – 5 31 31
[3] ∞6 ∞ 10 0 ∞ 15 62 62 62
29 [4] – 9–1 – – – – 91
[4] ∞ ∞ 1∞
2 ∞ 0 ∞ 28 28
8 [5] – – – – 4 –
[5] ∞ ∞ ∞ ∞ 2 0

After 3rd iteration i=2:

61dist [0] [1] [2] [3] [4] [5]61path [0] [1] [2] [3] [4] 6[5]1 61
-4 -4 -4 -4
[0] 310 13 9 7 18 12 [0]31 – 2 2 3 2 2 31 31
62 62 62 62
[1] ∞ 091∞ ∞ 5 ∞ [1] – 9–1 – – 4 – 91
2 2 2
 8 8 8
[2] ∞ 4 0 ∞ 9 3 [2] – 1 – – 1 5
[3] ∞ 14 10 0 19 13 [3] – 2 2 – 2 2

61[4] ∞ ∞ ∞ ∞ 0 ∞61 [4] – – – – – 6–1 61

-4 ∞ ∞ ∞ ∞ 2 0 -[5]
[5] 43 – – – – 4 – -4 -4
31 16 31 31
62 2 62 62
th 9 12 i=3: unchanged 912
After 4 iteration 91
8 8 28
th
After 5 iteration i=4: unchanged

After 6th iteration i=5:

61 61 61 61
-4 [0] [1] [2] [3] [4] [5] path
dist -4 [0] [1] [2] [3] [4] [5] -4 -4
31 31 31 31
[0] 06 13 9 7 14 12 [0] 6–2 2 2 3 2 2 62 62
29 9 91
[1] ∞ 0 1∞
2 ∞ 5 ∞ [1] – –12– – 4 – 28
8 [2] – 1 –
8 – 5 5
[2] ∞ 4 0 ∞ 5 3
[3] ∞ 14 10 0 15 13 [3] – 2 2 – 2 2

[4] ∞ ∞ ∞ ∞ 0 ∞ [4] – – – – – –
61 61 [5] – – – – 4
6–1 61
-4 ∞ ∞ ∞ ∞ 2 0 -4
[5] -4 -4
31 31 31 31
62 62 62 62
91♢Dynamic Data Structures♢ 91
COMP9024 24T1 [65/88] 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Floyd's 6Algorithm
1 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 algorithm is correct: 62
Why Floyd's 62 62
91 91 91
A shortest path2from
8 s to t using only nodes28from {0,…,i} is the shorter 2of8
a shortest path from s to t using only nodes from {0,…,i-1}
a shortest path from s to i using only nodes from {0,…,i-1}
61 6 i to t using only nodes from
plus a shortest path from
1- 6 {0,…,i-1}
1- 61
-4 43 43 -4
31 16 16 31
62 29 29 62
91 12 12
28 8 8

6Also 61 (can you see why?)

1- known as Floyd-Warshall algorithm 61 61
43 -4 -4 -4
1 31 31 31
COMP90246 29 ♢Dynamic Data Structures♢629
24T1 [66/88] 62 62
12 12 91
2
 8 8 8

<< ∧ >>
61❖ Exercise: Floyd's 6Algorithm
1- (cont) 61 61
-4 43 -4 -4
31 16 31 31
62 …
Cost analysis 29 62 62
91 12 91
2
initialising dist[][],
8 path[][] ⇒ O(E) 8 28
V iterations to update dist[][], path[][] ⇒ O(V3)

Time complexity of Floyd's algorithm: O(V3) (same as Warshall's algorithm for transitive
6closure)
1- 61 61 61
43 -4 -4 -4
16 31 31 31
29 62 62 62
12 91 91
8 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [67/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Digraph Applications
61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [68/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ PageRank 61 61 61
-4 -4 -4 -4
31 31 31 31
62
Goal: determine 62"important"
which Web pages are 62 62
91 91 91
28page contents; focus on 2hyperlinks
Approach: ignore 8 28
treat Web as graph: page = vertex, hyperlink = directed edge
pages with many incoming hyperlinks are important
61 61 degree" for vertices
need to compute "incoming 61 61
-4 -4 -4 -4
3 1 3 16 31 31
Problem:62the Web is a very large graph
2 62 62
9
approx. 10 114 pages, 10
91
15 hyperlinks 91
28 28 28
Assume for the moment that we could build a graph …

Most frequent operation in algorithm "Does edge (v,w) exist?"

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [69/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ PageRank (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62
Simple PageRank algorithm: 62 62 62
91 91 91
28
PageRank(myPage): 28 28
| rank=0
| for each page in the Web do
| | if linkExists(page,myPage) then
61|| || endrank=rank+1
if
6 1- 61 61
-4 43 -4 -4
| 3end
1 for 1 31 31
62 62 62 62
91 inbound link check
Note: requires 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [70/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ PageRank (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62 in Web, E = # hyperlinks62in Web
V = # pages 62 62
91 91 91
28 PageRank for each representation:
Costs for computing 28 28
Representation linkExists(v,w) Cost
Adjacency matrix edge[v][w] 1
61 61 61 61
-4
Adjacency lists -4
inLL(list[v],w) ≅ E/V -4 -4
31 31 31 31
62 62 62 62
Not feasible9…
1 91 91
28 28 28
adjacency matrix … V ≅ 1014 ⇒ matrix has 1028 cells
adjacency list … V lists, each with ≅10 hyperlinks ⇒ 1015 list nodes

6So
1-how to really do it? 61- 61 61
43 43 -4 -4
COMP90241624T1 ♢Dynamic Data Structures♢
16
[71/88]
31 31
29 29 62 62
12 12 91
2
 8 8 8

<< ∧ >>
61❖ PageRank (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62the random web surfer 62
Approach: 62 62
91 91 91
28 follow links in the web …28
if we randomly 28
… more likely to re-discover pages with many inbound links

curr=random page, prev=null

61for a long time do 61 61 61
|-4 if curr not in array -rank[]
4 then -4 -4
| 31 rank[curr]=0 31 31 31
| end 2
6 if 62 62 62
91 91 91
28
| rank[curr]=rank[curr]+1 28 28
| if random(0,100)<85 then // with 85% chance ...
| prev=curr
| curr=choose hyperlink from curr // ... crawl on
| else
61| curr=random page61 // avoid6getting stuck
1- 61
|-4 prev=null -4 43 -4
3
| end 16 if 3 16 16 31
62
end for29 29 29
12 12 12
 8 8 8
Could be accomplished while we crawl web to build search index

COMP9024 24T1 ♢Dynamic Data Structures♢ [72/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Implementing 61 Facebook 61 61
-4 -4 -4 -4
31 31 31 31
Facebook62could be considered as a giant
62 "social graph" 62 62
91 91 91
28vertices?
what are the 28 28
what are the edges?
are edges directional?
6What 61 …
1- kind of algorithm would 61 61
4help -4 -4 -4
31 us find people that you might
31 like to "befriend"? 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [73/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Network Flow 61 61 61
-4 -4 -4 -4
31 31 31 31
62is out of the scope for this6term.
This topic 29 62 62
91 12 91
2
This is not going8to be examined or assessed.8 28
We will leave the slides for your reference.

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [74/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Merchandise61 Distribution 61 61
-4 -4 -4 -4
31 31 31 31
62 Company …
Lucky Cricket 62 62 62
91 91 91
28 balls in Fairfield 28
produces cricket 28
has a warehouse in Rozelle that stocks them
ships them from factory to warehouse by leasing space on trucks with limited
capacity:
61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6What 61 …
1- kind of algorithm would 61 61
43 -4 -4 -4
16 31 31 31
29 62 62 62
12 91 91
2 2
 8 8 8
help us find the maximum number of crates that can be shipped from Fairfield to
Rozelle per day?

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [75/88] 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Flow Networks 61 61 61
-4 -4 -4 -4
31 31 31 31
62 …
Flow network 62 62 62
91 91 91
28 G=(V,E)
weighted graph 28 28
distinct nodes s∈V (source), t∈V (sink)

Edge weights denote capacities

61 61 61 61
-4
Applications: -4 -4 -4
31 31 31 31
62 networks, e.g.
Distribution 62 62 62
91 91 91
28
source: oil field 28 28
sink: refinery

edges: pipes

61 Traffic flow 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [76/88]
31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Flow Networks (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
Flow in a6network
29 62 f(v,w) for all vertices v,w∈V
G=(V,E) … nonnegative 62 such that 62
12 91 91
28 ∈ E
8 for each edge e=(v,w,capacity)
f(v,w)≤capacity
28
f(v,w)=0 if no edge between v and w
total flow into a vertex = total flow out of a vertex:
61 61 for all v ∈ V \ {s,t}
61 61
-4∑ f (x, v) = ∑ f (v, y)
-4 -4 -4
31
x∈V y∈V 31 31 31
62 62 62 62
9 9
12… no other flow from s to1t2has larger value
Maximum flow
91
8 8 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [77/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Flow Networks (cont)
61 61 61
-4 -4 -4 -4
31 31 31 31
Example:62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
9
A (maximum)1flow
91 91
2 …
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [78/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Augmenting Paths 61 61 61
-4 -4 -4 -4
31 31 31 31
Assume6 62
…2 f(v,w) contains current flow 62 62
91 91 91
28 any path from source s to
Augmenting path: 28sink t that can currently take
28 more flow
Example:

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [79/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Residual Network 61 61 61
-4 -4 -4 -4
31 31 31 31
Assume6 62flow f(v,w)
…2 flow network G=(V,E) and 62 62
91 91 91
28 (V,E'):
Residual network 28 28
same vertex set V
for each edge v →c w ∈ E …
61 6 61 61
-4 f(v,w) < c ⇒ add edge1(v
-4→c-f(v,w) w) to E' -4 -4
31 31f(v,w) 31 31
62 > 0 ⇒ add edge (v ← 62 w) to E'
f(v,w) 62 62
91 91 91
28 28 28
Example:

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [80/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Augmenting 61 Paths and Residual
61 Networks 61
-4 -4 -4 -4
31 31 31 31
62
Find an augmenting path in: 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
9
and show the1residual 12 9
network after augmenting the flow
91
2 8 8 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [81/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
611. Augmenting path: 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
316 additional flow = 1
maximum
31 31 31
29 62 62 62
12 91 91
2. Residual network: 28 28
8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
Can you find a further augmenting path in the new residual network?
COMP9024 24T1 ♢Dynamic Data Structures♢ [82/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Edmonds-Karp Algorithm
61 61 61
-4 -4 -4 -4
31 31 31 31
62 to solving maximum flow
One approach 62 problem … 62 62
91 91 91
maxflow(G): 28 28 28
1. Find a shortest augmenting path
2. Update flow[][] so as to represent residual graph
613. Repeat until no augmenting
61 path can be found 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [83/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Edmonds-Karp Algorithm
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Algorithm: 62 62 62
91 91 91
flow[][] //2V×V
8 array of current flow 28 28
visited[] /* array of predecessor nodes on shortest path
from source to sink in residual network */

61maxflow(G): 6 1
|- Input flow network G- with source s and sink
6 1-t 61
4 Output maximum flow value
43 43 -4
| 3 1 1 1 31
| 6 29 6 29 62 62
| initialise12 flow[v][w]=0 for all12vertices v, w 91
| maxflow=0 8 8 28
| while ∃shortest augmenting path visited[] from s to t do
| | df = maximum additional flow via visited[]
| | // adjust flow so as to represent residual graph
61| | v=t 61 61 61
|-4 | while v≠s do -4 -4 -4
| 3 |1 | flow[visited[v]][v] 31= flow[visited[v]][v]3+1 df; 31
6 6
| | |29flow[v][visited[v]] = 2flow[v][visited[v]] -
6df;
29 62
12
| | | v=visited[v]
9 12 12
 8 8 8
| | end while
| | maxflow=maxflow+df
| end while
61 | return maxflow 6 61 61
-4 1- -4 -4
Shortest
4
31 augmenting path can be3found by standard BFS 31 31
62 1 62 62 62
91 91 91
28 Data Structures♢
COMP9024 24T1 ♢Dynamic 28
[84/88] 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Edmonds-Karp Algorithm61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Time complexity analysis … 62 62 62
91 91 91
28 number of augmenting 2paths
Theorem. The 28.
8 needed is at most V·E/2
⇒ Outer loop has O(V·E) iterations.
Finding augmenting path ⇒ O(E) (consider only vertices connected to source and sink ⇒
O(V+E)=O(E))
61 61 61 61
-4 cost of Edmonds-Karp-4algorithm: O(V·E2)
Overall -4 -4
31 31 31 31
62 62 62
Note: Edmonds-Karp algorithm is an implementation of general Ford-Fulkerson method
62
91 91 91
28 28 28

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [85/88]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Edmonds-Karp
61 Algorithm 61 61
-4 -4 -4 -4
31 31 31 31
Show how62Edmonds-Karp algorithm6runs
2 on: 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
flow [0] [1] [2] [3] [4] [5] c-f [0] [1] [2] [3] [4] [5]
[0] [0] 2 3
61[1] 61 [1] 3 1 61 61
-4
[2]
-[2]
43 1 1
-4 -4
3 16 1 31 31
[3] 29 [3] 62 2 62 62
12 91 91
2 2
 8 8 8
[4] [4] 3
[5] [5]

61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [86/88] -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4 [0] [1] [2] [3] [4] [5] c-f
flow -4 [0] [1] [2] [3] [4] [5] -4 -4
31 31 31 31
[0] 06 0 0 0 0 0 [0] –6 2 3 – – – 62 62
29 29 91
[1] 0 0 120 0 0 0 [1] – – 12
– 3 1 – 28
8 8
[2] 0 0 0 0 0 0 [2] – – – 1 1 –
[3] 0 0 0 0 0 0 [3] – – – – – 2
[4] 0 0 0 0 0 0 [4] – – – – – 3
61[5] 0 0 0 0 0 061 [5] – – – – –
6– 1 61
-4 -4 -4 -4
31 31 31 31
62 path: 0-1-3-5, df: 2 62
augmenting 62 62
91 91 91
28 28 28
flow [0] [1] [2] [3] [4] [5] c-f [0] [1] [2] [3] [4] [5]
[0] 0 2 0 0 0 0 [0] – 0 3 – – –
[1] -2 0 0 2 0 0 [1] 2 – – 1 1 –
61[2] 0 0 0 0 0 061 [2] – – – 1 1 61
– 61
-4 -4 -4 -4
[3] 310 -2 0 0 0 2 [3]31– 2 – – – 0 31 31
62 62 62 62
[4] 0 09 0 0 0 0 [4] – –9 – – – 3 91
12 12 2
 8 8 8
[5] 0 0 0 -2 0 0 [5] – – – 2 – –

augmenting path: 0-2-4-5, df: 1

61 61 61 61
-4 [0] [1] [2] [3] [4] [5] c-f
flow -4 [0] [1] [2] [3] [4] [5] -4 -4
31 31 31 31
[0] 0622 1 0 0 0 [0] –620 2 – – – 62 62
91 91 91
[1] -2 0 20 8 2 0 0 [1] 2 – 2–8 1 1 – 28
[2] -1 0 0 0 1 0 [2] 1 – – 1 0 –
[3] 0 -2 0 0 0 2 [3] – 2 – – – 0
[4] 0 0 -1 0 0 1 [4] – – 1 – – 2
61 61 61 61
-4 0
[5] 0 0 -2 -1 0-[5]
4 – – – 2 1 – -4 -4
31 31 31 31
62 path: 0-2-3-1-4-5, df: 162
augmenting
62 62
91 91 91
28 28 28
flow [0] [1] [2] [3] [4] [5] c-f [0] [1] [2] [3] [4] [5]
[0] 0 2 2 0 0 0 [0] – 0 1 – – –
[1] -2 0 0 1 1 0 [1] 2 – – 2 0 –
61[2] -2 0 0 1 1
6
0 1-[2] 2 – – 0 0
6
– 1-
61
-4 43 43 -4
[3] 310 -1 -1 0 0 2 [3] 1– 1 1 – – 0 16 31
62 62 29 62
[4] 0 -1 91-1 0 0 2 [4] – 191 1 – – 1 12
2 2
 8 8 8
[5] 0 0 0 -2 -2 0 [5] – – – 2 2 –

COMP9024 24T1 ♢Dynamic Data Structures♢ [87/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧
61❖ Summary 61 61 61
-4 -4 -4 -4
31 31 31 31
62 weighted graphs: representations,
Digraphs, 62 applications 62 62
91 91 91
Reachability
28 28 28
Warshall
Minimum Spanning Tree (MST)
Kruskal, Prim
61 61 61 61
-4Shortest path problems -4 -4 -4
31Dijkstra (single source SPP)
31 31 31
62 62 62 62
91(all-pair SSP)
Floyd 91 91
28 28 28

Suggested reading (Sedgewick):

digraphs … Ch. 19.1-19.3

61 61 61 61
-4 weighted graphs … Ch. 20-20.1-4 -4 -4
31 31 31 31
62
MST … Ch. 20.2-20.4 62 62 62
91 91 91
2 2 2
 8 8 8
SSP … Ch. 21-21.3

COMP9024 24T1 ♢Dynamic Data Structures♢ [88/88]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

Produced: 11 Mar 2024

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2