Q1) You are given a directed graph G = (V, E) representing a computer network, in which each link (edge) e has a probability of 0 < pe < 1 to be alive. That means that at any given time, with probability pe, the link is up, and with probability 1 - pe, it is down. Assume that each link is up or down independently of all other links.

(a) You need to send lots of packets from s to t, but find the network is too unreliable. You plan to find the most unreliable path from s to t so you can upgrade it to achieve higher reliability. That is, you want to find a path P with the lowest probability of having all links in P up simultaneously. Construct a weighted graph G' = (V', E') such that you can use one call to the Bellman-Ford algorithm to find such a path. Prove that your algorithm is correct and that it has polynomial running time (in |V| and |E|). Assume the graph is acyclic. Hint: Recall, that a probability of two independent events x and y occurring simultaneously is Pr(x) * Pr(y) and that log(a*b) = log a + log b.

(b) Repeat part (a) without constructing G' or using the Bellman-Ford algorithm. Assume once again that the graph is acyclic. Prove that your algorithm runs in O(|V| + |E|) time. Hint: start by topologically sorting the vertices.

(c) You want to send an important packet from s to t along a single path, and therefore want to choose the path P with the highest probability of having all links in P up simultaneously. Construct another weighted graph G' = (V', E') such that you can use one call to Dijkstra's algorithm on G' to find such a path. Prove that your algorithm is correct and that it has polynomial running time (in |V| and |E|).