Find the most reliable path - Dijkstra’s algorithm

user_13758473 0
Viewed 1633

We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v), which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability of a communication channel from vertex u to vertex v. We interpret r(u, v) as the probability that the channel from u to will not fail, and we assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices.

     a
    / \
   b<--c         a directed to c; c directed to b; b directed to a

Let's say this is graph G = (V, E); vertex a is the root, one of the edge is a to c. a = u & c = v so edge is (u, v). I want to use Dijkstra’s algorithm to solve this, but not sure how.

     a
      \
   b<--c          path c: a -> c   &    b: a -> c -> b

Can someone explain the most reliable path in the simplest way possible?

This question is from Introduction to Algorithms, 3rd edition, chp 24.3

Thanks in advance!

dijkstra computer-science graph data-structures algorithm
1 Answers

We interpret r(u, v) as the probability that the channel from u to will not fail, and we assume that these probabilities are independent.

From this you can deduce that the probability that a given path will not fail is equal to the product of the r(u,v) of all edges (u,v) that make up the path.

You want to maximize that product.

This is exactly like the shortest path problem, for which you surely know an algorithm, except instead of minimizing a sum, you are trying to maximize a product.

There is a cool tool to go from products to sums: it's the logarithm. Logarithm is an increasing function, thus maximizing a product is the same as maximizing the logarithm of that product. But logarithm has the additional cool property that the logarithm of a product is equal to the sum of the logarithms:

log(a * b * c * d * ...) = log(a) + log(b) + log(c) + log(d) + ...

Thus maximizing the product of the reliabilities r(u,v) is the same as maximizing the sum of the log-reliabilities log(r(u,v)).

Since the reliabilities are probabilities of the edges, they are values between 0 (excluded) and 1 (included). You can exclude 0 because if an edge had a reliability of 0, you can remove that edge from the graph. Since 0 < r(u,v) <= 1, it follows that log(r(u,v)) is negative or 0.

So you are trying to maximize a sum of negative values. This is exactly the same as minimizing the sum of the opposite values.

Thus: apply your shortest-path algorithm, using -log(r(u,v)) as the lengths of the edges.

user_30807230
Related