Transcript PPT

CSCI-256
Data Structures & Algorithm Analysis
Lecture 11
Note: Some slides by Kevin Wayne.
Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.
Shortest Path Problem
• 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
– Bellman-Ford algorithm finds shortest paths in a graph with
negative cost edges (or reports the existence of a negative cost
cycle).
a
6
4
-4
-3
s
4
e
c
-2
3
2
3
6
g
b
f
7
4
Minimum Spanning Tree
• Minimum spanning tree: Given a connected graph G =
(V, E) with real-valued edge weights ce, a MST is a
subset of the edges T  E such that T is a spanning tree
whose sum of edge weights is minimized
24
4
23
6
16
4
18
5
9
5
11
8
14
10
9
6
7
8
11
7
21
G = (V, E)
T, eT ce = 50
Applications
• MST is a fundamental problem with diverse applications
– Network design
• telephone, electrical, hydraulic, TV cable, computer, road
– Approximation algorithms for NP-hard problems
• traveling salesperson problem, Steiner tree
– Indirect applications
•
•
•
•
•
•
•
max bottleneck paths
LDPC codes for error correction
image registration with Renyi entropy
learning salient features for real-time face verification
reducing data storage in sequencing amino acids in a protein
model locality of particle interactions in turbulent fluid flows
autoconfig protocol for Ethernet bridging to avoid cycles in a
network
– Cluster analysis
Greedy Algorithms
• Kruskal's algorithm
– Start with T = . Consider edges in ascending order of cost.
Insert edge e in T unless doing so would create a cycle
• Reverse-Delete algorithm
– Start with T = E. Consider edges in descending order of cost.
Delete edge e from T unless doing so would disconnect T
• Prim's algorithm
– Start with some root node s and greedily grow a tree T from s
outward. At each step, add the cheapest edge e to T that has
exactly one endpoint in T
• Remark: All three algorithms produce a MST
Greedy Algorithm 1:
Kruskal’s Algorithm
• Add the cheapest edge that joins disjoint
components
15
t
a
3
10
Construct the MST
with Kruskal’s
algorithm
Label the edges in
order of insertion
14
9
13
s
17
1
4
e
c
20
2
5
7
b
u
6
8
12
16
v
11
g
f
22
Greedy Algorithm 2:
Reverse-Delete Algorithm
• Delete the most expensive edge that does not
disconnect the graph
15
t
a
3
10
Construct the MST
with the reversedelete algorithm
Label the edges in
order of removal
14
9
13
s
17
1
4
e
c
20
2
5
7
b
u
6
8
12
16
v
11
g
f
22
Greedy Algorithm 3:
Prim’s Algorithm
• Extend a tree by including the cheapest out
going edge
15
t
a
3
10
Construct the MST
with Prim’s
algorithm starting
from vertex a
Label the edges in
order of insertion
14
9
13
s
17
1
4
e
c
20
2
5
7
b
u
6
8
12
16
v
11
g
f
22
Why do the greedy algorithms work?
• All these algorithms work by repeatedly inserting
or deleting edges from a partial solution
– Thus to analyze these algorithms, it would be useful
to have in hand some basic facts saying when it is
“safe” to include an edge in the MST or when it is
“safe” to eliminate and edge on the grounds that it
couldn’t possible be in the MST
• For simplicity, assume all edge costs are distinct.
Thus, we can refer to “the MST”
When is it safe to include an edge in the
MST?
• Edge inclusion lemma
– Let S be a subset of V, and suppose e = (u, v) is the
minimum cost edge of E, with u in S and v in V-S
– e is in every MST of G. Or equivalently, if e is not in T,
then T is not a MST
e
S
V-S
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 e1 = (u1, v1) with u1 in S
and v1 in V-S
e is the
minimum cost
edge between
S and V-S
e1
S
e
V-S
• T1 = T – {e1} + {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
• Show that when an edge is added to the MST by
Prim or Kruskal, the edge is the minimum cost
edge between S and V-S for some set S
Prim’s Algorithm
S = { };
T = { };
while S != V
choose the minimum cost edge
e = (u,v), with u in S, and v in V-S
add e to T
add v to S
Prove Prim’s algorithm computes an MST
• Show an edge e is in the MST when it is added
to T
Kruskal’s Algorithm
Let C = {{v1}, {v2}, . . ., {vn}}; T = { }
while |C| > 1
Let e = (u, v) with u in Ci and v in Cj be the
minimum cost edge joining distinct sets in C
Replace Ci and Cj by Ci U Cj
Add e to T
Prove Kruskal’s algorithm computes an MST
• Show an edge e is in the MST when it is added
to T
When can we guarantee an edge is not in
the MST?
• Cycle lemma
– The most expensive edge on a cycle is never in a
MST
e1
S
e
V-S
e is the most
expensive edge
on a cycle
involving S and
V-S
– Optimality of Reverse-Delete algorithm follows from
this
Dealing with the assumption of no equal
weight edges
• Force the edge weights to be distinct
– Add small quantities to the weights
– Give a tie breaking rule for equal weight edges