Counterexample to this modified Dijkstra's 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.
Your algorithm makes the wrong choice between the following two paths:


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