Problem 1. Shortest pathsGive 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...

Hi! I need help with these questions


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 corresponding (augmenting) paths.