4. (Extra credit, up to 10 points) In this question, we'll consider a different type of "best path" problem. Suppose we have as input G = (V,E) where V = {1,2,...,N} consists of a set of cities and E a set of roads connecting those cities. These roads, however, are littered with bandits. For each edge (i, j) E, you have an estimate p(i, j) of the probability that you can travel from city i to city j successfully (i.e., without being robbed). The probability2 of being not being robbed along a path

(i1, i2), (i2, i3), ..., (ik1, ik)

is the product of the probabilities of not being robbed on each road in the path:

p(i1,i2)p(i2,i3)p(ik1,ik).

You want to find the best path from 1 to N, where "best path" means the maximum probability of getting from 1 to N without being robbed3. This is different from our normal shortest-path problem in two key ways: we're trying to maximize something instead of minimize something, and along a route we multiply edge probabilities rather than add edge lengths. Argue that we can still model this problem as a shortest path problem by being clever about the edge lengths, and moreover, we can do so with edge lengths being nonnegative.