5
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
1
$\begingroup$

"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: \begin{equation} a + b > c + d \implies \frac{a + b}{a \times b} < \frac{c + d}{c \times d} \end{equation} Which is eqivalent to saying: \begin{equation} \frac{c \times d}{a \times b} < \frac{c + d}{a + b} < 1 \end{equation} Which is incorrect. To find counter-examples, you just need to find numbers a, b, c and d, such that: \begin{equation} a + b > c + d, \quad a \times b < c \times d \end{equation} There are many, for instance (9, 2) (5, 5).
Here, \begin{equation} \frac{1}{11} < \frac{1}{10}, \quad but \quad \frac{1}{9} + \frac{1}{2} > \frac{1}{5} + \frac{1}{5} \end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.