Problem 1. Shortest paths
Give an efficient algorithm to count the total number of paths from s to each vertex v in a directed acyclic graph.
Analyze your algorithm.
Problem 2. Johnson's algorithm
Suppose we do not want to create a new source vertex in G and instead pick any vertex of G as s.
(a) Give an example of a graph G with a negative-weight cycle where this algorithm fails.
(b) Give an example of a graph G without a negative-weight cycle where this algorithm fails.
Problem 3. Max fiow
Make a small graph G for the maximum flow problem such that the Edmonds-Karp algorithm uses fewer aug-
mentations on than the Ford-Fulkerson algorithm. Show the augmenting paths computed by both algorithms.
Problem 4. Max flow
There are n undergraduate students and k departments at some university. The Student Senate must have k
students, one from each department. It also should have k; freshmen, k; sophomores, ks juniors, and k; seniors
where ky + ky + ks + ky = k. The task is to decide if the Student Senate can be formed. If it can be formed, find
a solution with k students. Design an algorithm for this task using max flow.
Problem 5. Max flow/min cut
Let G be the graph shown below.
(a) Enumerate all cuts in G and show their capacities.
(b) Find all minimum cuts in G. Also find a maximum cut (a cut with maximum capacity).
(¢) Find maximum flow in G using the Ford-Fulkerson algorithm. Show the flow value and the co
esponding
(augmenting) paths.