Analysis of Algorithms
V. Adamchik CSCI 570
Lecture 5
University of Southern California
Greedy Algorithms
Reading: chapter 4
Homework – 2
We do not have enough time to cover the master theorem this week. Therefore, you do not need to solve the last homework problem #5, it will be a part of the next Hw-3 assignment.
The Minimum Spanning Tree
Find a spanning tree of the minimum total weight.
MST is fundamental problem with diverse applications.
Kruskal’s Algorithm algorithm builds a tree one EDGE at a time.
– Sort all edges by their weights.
– Loop:
– Choose the minimum weight edge and join correspondent vertices (subject to cycles).
– Go to the next edge.
– Continue to grow the forest until all vertices are connected.
Sorting edges – O(E log E)
Cycle detection – O(V) for each edge
Total: O(V*E + E*log E)
Prim’s Algorithm
algorithm builds a tree one VERTEX at a time.
– Start with an arbitrary vertex as a sub-tree C.
– Expand C by adding a vertex having the minimum weight edge of the graph having exactly one end point in C.
– Update distances from C to adjacent vertices.
– Continue to grow the tree until C gets all vertices.
deleteMin – O(V), for each vertex update(decreaseKey) – O(log V ), for each edge
Total: O(V log V + E log V)
Discussion Problem
Assume that an unsorted array is used instead of a binary heap. What would the running time of the Prim algorithm?
Assume that we need to find an MST in a dense graph using Prim’s algorithm. Which implementation (heap or array) shall we use?
MST: Proof of the correctness
A cut of a graph is a partition of its vertices into two disjoint sets (blue and green vertices below.)
A crossing edge is an edge that connects a vertex in one set with a vertex in the other.
The smallest crossing edge must be in the MST.
a
1
b2c1d
357 e3f
4
2
MST: Proof of the correctness Lemma: Given any cut in a weighted graph , the crossing
edge of minimum weight is in the MST of the graph.
G-X
X
e
v u
Review Questions
(T/F) The first edge added by Kruskal’s algorithm can be the last edge added by Prim’s algorithm.
(T/F) Suppose we have a graph where each edge weight value appears at most twice. Then, there are at most two minimum spanning trees in this graph.
(T/F) If a connected undirected graph G = (V, E) has V + 1 edges, we can find the minimum spanning tree of G in O(V) runtime.
The Shortest Path Problem
Edsger Dijkstra (1930-2002)
The Shortest Path Problem
Given a positively weighted graph G with a source vertex s, find the shortest path from s to all other vertices in the graph.
1
24 2
5 19
11
9
S
18 14
2
30
4
5
3
16
20
5
16
6
6 44 7
The Shortest Path Problem
What is the shortest distance from s to 4?
1
24 2
5 19
11
9
S
18 14
2
30
4
5
3
16
20
5
16
6
6 44 7
Greedy Approach
When algorithm proceeds all vertices are divided into two groups
– vertices whose shortest path from the source is known
– vertices whose shortest path from the source is NOT discovered yet
Move vertices one at a time from the undiscovered set of vertices to the known set of the shortest distances, based on the shortest distance from the source.
solution tree = s
heap = {1, 2, 3, 4, 5, 6, 7}
24 2 1
9
0
s
14
18
5 30
2
19
5
3
11 16
5 16
4 20
6 44 7
6
solution tree = { s }
heap = {1, 2, 3, 4, 5, 6, 7}
decreaseKey
9
24 2 1
9
14
s
14 18
5 30
2
19
5
3
11 16
5 16
4 20
16
6 44 7
6
solution tree = { s }
heap = {1, 2, 3, 4, 5, 6, 7}
deleteMin
24 2 1
9
9
14
s
14 18
5 30
2
19
5
3
5 16
4 20
11 16
16
6 44 7
6
solution tree = { s, 1 } heap = {2, 3, 4, 5, 6, 7}
24 2 1
9
9
14
s
14 18
5 30
2
19
5
3
5 16
4 20
11 16
16
6 44 7
6
solution tree = { s, 1 } heap = {2, 3, 4, 5, 6, 7}
9
1
decreaseKey 24 2
5
3
33
9
14
s
14 18
5 30
2
19
11 16
5 16
4 20
16
6 44 7
6
solution tree = { s, 1 } heap = {2, 3, 4, 5, 6, 7}
24 2
1 deleteMin
9 1418 14 5 30
9
4 16
33
2
19
5
3
11 16
s
16 5 20
6
6 44 7
solution tree = { s, 1, 5 } heap = {2, 3, 4, 6, 7}
24 2 1
9
33
9
14
s
14 18
5 30
2
19
5
3
5 16
4 20
11 16
16
6 44 7
6
solution tree = { s, 1, 5 } heap = {2, 3, 4, 6, 7}
24 2 1
32
9
9
14
s
5 16
14 18
5 30
4
44
2
19
11
5
3
16
20
16
6 44 7
6 deleteMin
solution tree = { s, 1, 5, 6 } heap = {2, 3, 4, 7}
32
24 2 91
9 14182 14 5 30
s 436
16 5 20
5
19
11
3
6
16
16
44 7
6
60
solution tree = { s, 1, 5, 6, 2, 4, 3, 7 } heap = {}
32
14182 5
530 19 45
24 2 91
9
14
s
5 16
34 11 3 4
16
20
16
50
7
6
6
44
Complexity
Let D(v) denote a length from the source s to vertex v. We store distances D(v) in a binary heap.
Discussion Problem
Assume that an unsorted array is used instead of a binary heap. What would the running time of the Dijkstra algorithm?
Proof of Correctness
Lemma. For each node u S (solution tree), d(u) is the shortest s-u path.
P
d
S
26
Proof of Correctness
s
S
u
v
27
Discussion Problem 1
You are given a graph representing the several career paths available in industry. Each node represents a position and there is an edge from node v to node u if and only if v is a pre-requisite for u. Top positions are the ones which are not pre-requisites for any positions. Start positions are the ones which have no pre- requisites. The cost of an edge (v,u) is the effort required to go from one position v to position u. Salma wants to start a career and achieve a top position with minimum effort. Using the given graph can you provide an algorithm with the same run time complexity as Dijkstra’s algorithm?
8
VP1
758654 8
CEO
COO CTO
6
10
132
Dir2
6
142
Prog
VP2 VP3 VP4
4754
VP5
5
3
QA
Dir1
Dir3
Dir4
MKT
ADV
Discussion Problem 2
Design a linear time algorithm to find shortest distances in a DAG.
3a S547
e -1 -3 d
22b
6
1
c
Review Questions
(T/F) If all edges in a connected undirected graph have distinct positive weights, the shortest path between any two vertices is unique.
(T/F) Suppose we have calculated the shortest paths from a source to all other vertices. If we modify the original graph, G, such that weights of all edges are increased by 2, then the shortest path tree of G is also the shortest path tree of the modified graph.
(T/F) Suppose we have calculated the shortest paths from a source to all other vertices. If we modify the original graph G such that weights of all edges are doubled, then the shortest path tree of G is also the shortest path tree of the modified graph.
Discussion Problem 3
Why Dijkstra’s greedy algorithm does not work on graphs with negative weights?
S5A 5
3
C -9 B
Discussion Problem 4
In this problem you are to find the most efficient way to deliver power to a network of n cities. It costs pi
to open up a power plant at city i. It costs cij ≥ 0 to put a cable between cities i and j. A city is said to have power if either it has a power plant, or it is connected by a series of cables to some other city with a power plant. Devise an efficient algorithm for finding the minimum cost to power all the cities.
Discussion Problem 5
Hardy decides to start running to work in San Francisco to get in shape. He prefers a route to work that goes first entirely uphill and then entirely downhill. To guide his run, he prints out a detailed map of the roads between home and work. Each road segment has a positive length, and each intersection has a distinct elevation. Assuming that every road segment is either fully uphill or fully downhill, give an efficient algorithm to find the shortest path that meets Hardy’s specifications.
3
0 9 10 8 1
57 6
Home
Work
4
Discussion Problem 6
Given a graph G=(V,E) whose edge weights are integers in the range [0, W], where W is a relatively small integer number compare to the number of vertices, W = O(1). We could run Dijkstra’s algorithm to find the shortest distances from the start vertex to all other vertices. Design a new linear time algorithm that will outperform Dijkstra’s algorithm.
Solution