Find least probable path in graph

Question

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?

• G. Bach: If you want the least probable path, wouldn't that just be the one with the smallest weight, not the largest weight?
• Parham: 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.
• David Richerby: 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?

Answer 1

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. You can use the Bellman-Ford algorithm to find the shortest path in $G'$, and that will correspond to the path in $G$ with lowest 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.

• Federico Lebrón: The question asks "my aim is to find the least 'probable' path between two vertices". This answer gives the path "with highest probability", which is the opposite of what the question was asking.
• D.W.: @FedericoLebrón, thank you! I've edited my answer to correct this error.