patternMinor
Counterexample to this modified Dijkstra's
Viewed 0 times
thismodifiedcounterexampledijkstra
Problem
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.
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.
Solution
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$.
-
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$.
Context
StackExchange Computer Science Q#50267, answer score: 8
Revisions (0)
No revisions yet.