1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If you want the least probable path, wouldn't that just be the one with the smallest weight, not the largest weight? $\endgroup$ – G. Bach Dec 23 '13 at 14:01
  • $\begingroup$ You mean the longest path on $G'$? If so, then what does is have do to with Dijkstra's shortest path? However, even if longest path wasn't NP-hard, this reasoning would still be wrong. $\endgroup$ – Parham Dec 23 '13 at 15:15
  • $\begingroup$ This doesn't work at all. If the product of the weights along a path is the probability that the given path is taken, the probability that the path is not taken is the sum of the probabilities of all other paths, not the probability you describe. But I'm not even sure your original problem is well-defined: how do you know that all the "probabilities" sum to one, for example? $\endgroup$ – David Richerby Dec 24 '13 at 13:55
3
$\begingroup$

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.

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