[Solved]: Find least probable path in graph

Problem Detail: 

I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\_) = w(s, q)$ with $s,q \in V$), my aim is to find the least 'probable' path between two vertices.

My initial approach is to generate an graph $G'$ where the weights are the complementary probabilities $1- w(s, q)$ (with strictly positive values), and compute Dijkstra's shortest path on $G'$. Is this reasoning sound? Or am I getting myself into an NP-hard disaster?

Asked By : lkc

Answered By : D.W.

Your approach doesn't work. Presumably, you want to define the probability of a path to be the product of the probabilities on its edges. It sounds like you want to define the weight $w(e)$ on an edge $e$ to be $w(e)=1-p(e)$ (one minus its probability). However, doesn't work. It doesn't do what you want: you want $w(e)+w(e')$ to correspond to $p(e) \times p(e')$, but it doesn't.

Instead, you should be taking logarithms. In particular, you should define the weight on edge $e$ by $w(e) = -\log p(e)$. Now addition of weights corresponds to multiplication of probabilities:

$$w(e) + w(e') = -(\log p(e) + \log p(e')) = - \log(p(e) \times p(e')),$$

as desired. At this point all of the weights in $G'$ will be non-negative (do you see why?), so you can use Dijkstra's algorithm to find the shortest path in $G'$, and that will correspond to the path in $G$ with highest probability. As you can see, this is not a longest-path problem at all; it is just a straightforward shortest-paths problem.

The trick of taking logs to turn multiplication into addition is a standard one, including in many applications of graphs, so this is worth knowing.

Best Answer from StackOverflow

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