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

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$.
"Any function that maps smaller fractions to bigger numbers can be used" - This is correct but not what you are doing. What you are assuming is, for positive numbers a, b, c and d: $$a + b > c + d \implies \frac{a + b}{a \times b} < \frac{c + d}{c \times d}$$ Which is eqivalent to saying: $$\frac{c \times d}{a \times b} < \frac{c + d}{a + b} < 1$$ Which is incorrect. To find counter-examples, you just need to find numbers a, b, c and d, such that: $$a + b > c + d, \quad a \times b < c \times d$$ There are many, for instance (9, 2) (5, 5).
Here, $$\frac{1}{11} < \frac{1}{10}, \quad but \quad \frac{1}{9} + \frac{1}{2} > \frac{1}{5} + \frac{1}{5}$$