Consider a graph (V,E) where each edge (u, v) E has a weight r(u,v), 0 r(u,v) 1, which denotes the reliability of a communication channel from u to v. Specifically, r(u,v) is the probability that the channel from u to v will not fail. Assume these probabilities are independent among edges. Describe how we can utilize Dijkstras shortest path algorithm to find a most reliable path between two given nodes.

Hints:

(1) let p be a probability variable (i.e., 0 p 1); then p is larger if and only if -log p is smaller;

(2) log of the product of terms is equal to the sum of the log of terms, i.e., log(i pi) = i log pi