I am currently stuck on a a text book problem which asks me to use Dijkstra's Algorithm as is to find the path of highest probability. The question states that each edge is given a probability of $[0,1]$. To find the probability of a path in the graph $G=(V,E)$ we take $\prod_{e\epsilon P}P(e)$ such that $e \epsilon E$ and $P(e)$ is the probability along that edge $e$.
Since the edge weights are being multiplied instead of summed up we need to come up with some function $f(P(e))$ that will take our edge probabilities to to something we can pass to Dijkstra. In other words the path of highest probability in $G$ should be the shortest path in the graph $G' = (V',E')$.
My thinking is to use $f(P(e)) = -log(P(e))$ as the function since it is monotonically increasing. However, I'm not sure this is correct. What do you all think?
Thank you!
Best Answer
Yes, that's right. Since $P(e)$ is a probability, $-\log P(e)$ is non-negative, and then the length of a path $R$ is $\sum_{e\in R}(-\log P(e))=-\log\big(\prod_{e\in R}P(e)\big)$. So the shortest path is the one with highest probability.