Algorithms Minimum Spanning Trees Notes | EduRev

: Algorithms Minimum Spanning Trees Notes | EduRev

 Page 1


1
CSE 421
Algorithms
Richard Anderson
Lecture 10
Minimum Spanning Trees
Announcements
• Homework 3 is due now
• Homework 4, due 10/26, available now
• Reading
– Chapter 5
– (Sections 4.8, 4.9 will not be covered in class)
• Guest lecturers (10/28 – 11/4)
– Anna Karlin
– Venkat Guruswami
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Dijkstra’s Algorithm
Implementation and Runtime
S = {};    d[s] = 0;     d[v] = inf for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], d[v] + c(v, w))
s
u
v
z
y
x
Edge costs are assumed to be non-negative
a
b
HEAP OPERATIONS
n Extract Min
m Heap Update
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
Page 2


1
CSE 421
Algorithms
Richard Anderson
Lecture 10
Minimum Spanning Trees
Announcements
• Homework 3 is due now
• Homework 4, due 10/26, available now
• Reading
– Chapter 5
– (Sections 4.8, 4.9 will not be covered in class)
• Guest lecturers (10/28 – 11/4)
– Anna Karlin
– Venkat Guruswami
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Dijkstra’s Algorithm
Implementation and Runtime
S = {};    d[s] = 0;     d[v] = inf for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], d[v] + c(v, w))
s
u
v
z
y
x
Edge costs are assumed to be non-negative
a
b
HEAP OPERATIONS
n Extract Min
m Heap Update
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
2
Compute the bottleneck shortest 
paths
a
b
c
s
e
g
f
d
4
2
-3
6
6
5
4
-2
3
7
6
3
7
4
a
b
c
s
e
g
f
d
How do you adapt Dijkstra’s algorithm  
to handle bottleneck distances
• Does the correctness proof still apply?
Minimum Spanning Tree
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Greedy Algorithm 1
Prim’s Algorithm
• Extend a tree by including the cheapest 
out going edge
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Greedy Algorithm 2
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint 
components
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Greedy Algorithm 3
Reverse-Delete
• Delete the most expensive edge that does 
not disconnect the graph
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Page 3


1
CSE 421
Algorithms
Richard Anderson
Lecture 10
Minimum Spanning Trees
Announcements
• Homework 3 is due now
• Homework 4, due 10/26, available now
• Reading
– Chapter 5
– (Sections 4.8, 4.9 will not be covered in class)
• Guest lecturers (10/28 – 11/4)
– Anna Karlin
– Venkat Guruswami
Shortest Paths
• Negative Cost Edges
– Dijkstra’s algorithm assumes positive cost edges
– For some applications, negative cost edges make 
sense
– Shortest path not well defined if a graph has a 
negative cost cycle
a
b
c
s
e
g
f
4
2
-3
6
4
-2
3
4
6
3
7
-4
Negative Cost Edge Preview
• Topological Sort can be used for solving 
the shortest path problem in directed 
acyclic graphs
• Bellman-Ford algorithm finds shortest 
paths in a graph with negative cost edges 
(or reports the existence of a negative cost 
cycle).
Dijkstra’s Algorithm
Implementation and Runtime
S = {};    d[s] = 0;     d[v] = inf for v != s
While S != V
Choose v in V-S with minimum d[v]
Add v to S
For each  w in the neighborhood of v
d[w] = min(d[w], d[v] + c(v, w))
s
u
v
z
y
x
Edge costs are assumed to be non-negative
a
b
HEAP OPERATIONS
n Extract Min
m Heap Update
Bottleneck Shortest Path
• Define the bottleneck distance for a path 
to be the maximum cost edge along the 
path
s
v
x
u
6 5
5
3
4
2
2
Compute the bottleneck shortest 
paths
a
b
c
s
e
g
f
d
4
2
-3
6
6
5
4
-2
3
7
6
3
7
4
a
b
c
s
e
g
f
d
How do you adapt Dijkstra’s algorithm  
to handle bottleneck distances
• Does the correctness proof still apply?
Minimum Spanning Tree
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Greedy Algorithm 1
Prim’s Algorithm
• Extend a tree by including the cheapest 
out going edge
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Greedy Algorithm 2
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint 
components
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
Greedy Algorithm 3
Reverse-Delete
• Delete the most expensive edge that does 
not disconnect the graph
a
b
c
s
e
g
f
9
2
13
6
4
11
5
7
20
14
t
u
v
15
10
1
8
12
16
22
17
3
3
Why do the greedy algorithms 
work?
• For simplicity, assume all edge costs are 
distinct
• Let S be a subset of V, and suppose e = 
(u, v) be the minimum cost edge of E, with 
u in S and v in V-S
• e is in every minimum spanning tree
Proof 
• Suppose T is a spanning tree that does not 
contain e
• Add e to T, this creates a cycle
• The cycle must have some edge e
1
= (u
1
, v
1
) 
with u
1
in S and v
1
in V-S
•T
1
= T – {e
1
} + {e} is a spanning tree with lower 
cost
• Hence, T is not a minimum spanning tree
Optimality Proofs
• Prim’s Algorithm computes a MST
• Kruskal’s Algorithm computes a MST
Reverse-Delete Algorithm
• Lemma:  The most expensive edge on a 
cycle is never in a minimum spanning tree
Dealing with the assumption
• Force the edge weights to be distinct
– Add small quantities to the weights 
– Give a tie breaking rule for equal weight 
edges 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!