Carrying stones. You are given a directed acyclic graph G = (V, E) with n vertices and m edges, along with a node te V. At each vertex v EV, there are a number of stones q[u] (so q[u] is a nonnegative integer). In addition, each edge e E has a capacity c(e), which is a positive integer. Now, you can start out at any node with an empty bag, and then can travel along a path picking up stones along the way, adding them to your bag as you go: if the path visits node v, you can pick up q[u] stones and add them to your bag. However, whenever you traverse an edge along this path, the number of stones in your bag cannot exceed the capacity of this edge: if you have too many stones, you can drop some of them off before traversing the edge. You can think of each edge e as a "bridge that cannot support the weight of more than c(e) stones. Your goal is to find a path, starting at any node with empty bag, and ending at t, so that you arrive at t with as many stones as possible (if there are any stones at t itself, you can also add those to your bag). To simplify the problem, instead of computing an optimal path, just compute the number of stones that such an optimal path will yield. Show how to solve this problem in time O(n + m). Hint: Start by running a topological sorting algorithm on the reverse of the graph G. Then compute for each node v the value m[u], which is the maximum number of stones you can have in your bag when you arrive at node v (along any path in the original graph, starting at any node, including stones you pick up at v). Food for thought will not be graded): Suppose you are also given a node s EV as input, and the goal is to find the number of stones on an optimal path that starts at s and ends at t. How would you modify your algorithm? More food for thought (will not be graded): Suppose you also want to print out the optimal path itself. How would you modify your algorithm? 2 Even more food for thought (will not be graded): Suppose you are not allowed to drop any stones, and you also want to print out the optimal path, including the number of stones to pick up at each node along the path. How would you modify your algorithm? Carrying stones. You are given a directed acyclic graph G = (V, E) with n vertices and m edges, along with a node te V. At each vertex v EV, there are a number of stones q[u] (so q[u] is a nonnegative integer). In addition, each edge e E has a capacity c(e), which is a positive integer. Now, you can start out at any node with an empty bag, and then can travel along a path picking up stones along the way, adding them to your bag as you go: if the path visits node v, you can pick up q[u] stones and add them to your bag. However, whenever you traverse an edge along this path, the number of stones in your bag cannot exceed the capacity of this edge: if you have too many stones, you can drop some of them off before traversing the edge. You can think of each edge e as a "bridge that cannot support the weight of more than c(e) stones. Your goal is to find a path, starting at any node with empty bag, and ending at t, so that you arrive at t with as many stones as possible (if there are any stones at t itself, you can also add those to your bag). To simplify the problem, instead of computing an optimal path, just compute the number of stones that such an optimal path will yield. Show how to solve this problem in time O(n + m). Hint: Start by running a topological sorting algorithm on the reverse of the graph G. Then compute for each node v the value m[u], which is the maximum number of stones you can have in your bag when you arrive at node v (along any path in the original graph, starting at any node, including stones you pick up at v). Food for thought will not be graded): Suppose you are also given a node s EV as input, and the goal is to find the number of stones on an optimal path that starts at s and ends at t. How would you modify your algorithm? More food for thought (will not be graded): Suppose you also want to print out the optimal path itself. How would you modify your algorithm? 2 Even more food for thought (will not be graded): Suppose you are not allowed to drop any stones, and you also want to print out the optimal path, including the number of stones to pick up at each node along the path. How would you modify your algorithm
