[Solved]: Counterexample to this modified Dijkstra's

Problem Detail: 

In class, we were given the following problem:

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 v 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.

My answer was to run Dijkstra's shortest path algorithm taking (1 / r(u,v) ) as the weight for each edge, which is wrong. The standard solution to this problem is to take the -log(r(u,v)) when running Dijkstra's algorithm. I understand why the standard solution is correct as it exploits the log's property where: log(a*b) = log(a) + log(b) to convert the problem from maximizing the product to minimizing the sum of the logs. However, what is an example of a graph where taking the inverse of the reliability would not produce the optimal result? My thinking was that any function that maps smaller fractions to bigger numbers could be used.

Asked By : dramzy

Answered By : orlp

Your algorithm makes the wrong choice between the following two paths:

1. 5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$.

2. A single channel with a reliability of 8%, weight ${1 \over 0.08} = 12.5$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50267