2 Problem on shortest paths The input is a graph (V, E) in which edge e E E has positive length l(e), nodes st EV and a positive integer k. An s-t path P is a sequence of nodes, say vo..., Vi such that Vo = s, vi = t and (U;1, V) = ei E for j = 1,...,i. The length of P is i - k. For example, we want to get from city s to city t, the edges are bus connections, lle) is the price of connection e. We have k coupons that allow to use a connection (bus ride) for free, and we want to spend the minimum amount. Clearly, an optimum modification of a path with k or fewer edges has length zero, and for a path with more than k edges we change the k largest lengths to zero. Show that an optimum modification of a shortest s-t paths can be a wrong solution. Show how to find the correct solution in polynomial time. To get the largest number of points, the running time of your algorithm must be O(D(kn, km) where D(n, m) is the running time of Dijkstra's algorithm in a graph with n nodes and m edges. You may assume, Dijkstra's algorithm is known. The description of your method may have the form of a reduction: use the graph (V, E) and k to build a graph with at most ck|V| nodes and ck|E| edges such that the lengths of s-t paths in the new graph are the same as the u-modified lengths in the original graph. 2 Problem on shortest paths The input is a graph (V, E) in which edge e E E has positive length l(e), nodes st EV and a positive integer k. An s-t path P is a sequence of nodes, say vo..., Vi such that Vo = s, vi = t and (U;1, V) = ei E for j = 1,...,i. The length of P is i - k. For example, we want to get from city s to city t, the edges are bus connections, lle) is the price of connection e. We have k coupons that allow to use a connection (bus ride) for free, and we want to spend the minimum amount. Clearly, an optimum modification of a path with k or fewer edges has length zero, and for a path with more than k edges we change the k largest lengths to zero. Show that an optimum modification of a shortest s-t paths can be a wrong solution. Show how to find the correct solution in polynomial time. To get the largest number of points, the running time of your algorithm must be O(D(kn, km) where D(n, m) is the running time of Dijkstra's algorithm in a graph with n nodes and m edges. You may assume, Dijkstra's algorithm is known. The description of your method may have the form of a reduction: use the graph (V, E) and k to build a graph with at most ck|V| nodes and ck|E| edges such that the lengths of s-t paths in the new graph are the same as the u-modified lengths in the original graph