Consider the problem of finding the shortest path from s to all nodes in a graph G = (V, E). In class, we showed that this can be done by solving just one network flow problem. a) The solution to the network flow problem gives you flows on every edge. How would you actually get the shortest path from s to a particular node i. (Hint: You can assume that there is only one best shortest path to each node i. Argue that the flow into node i comes from just one edge.) b) Consider the same problem, but now we want each edge to be used in at most k of the shortest paths that we are computing. (Recall we are computing VI - 1 shortest paths overall). How would we solve this as a network flow problem? c) Given an example of a graph that does not have a solution to b) when k = 2. d) From part b), how can we find the smallest value of k that will result in a feasible solution. Provide an algorithm or optimization problem to solve this. Consider the problem of finding the shortest path from s to all nodes in a graph G = (V, E). In class, we showed that this can be done by solving just one network flow problem. a) The solution to the network flow problem gives you flows on every edge. How would you actually get the shortest path from s to a particular node i. (Hint: You can assume that there is only one best shortest path to each node i. Argue that the flow into node i comes from just one edge.) b) Consider the same problem, but now we want each edge to be used in at most k of the shortest paths that we are computing. (Recall we are computing VI - 1 shortest paths overall). How would we solve this as a network flow problem? c) Given an example of a graph that does not have a solution to b) when k = 2. d) From part b), how can we find the smallest value of k that will result in a feasible solution. Provide an algorithm or optimization problem to solve this