Right now, your code has
do if val[x] + p(x, y) < val[y]:
val[y] = val[x] + p(x, y)
Since the edge weights in this case represent probabilities, you need to multiply them together (rather than adding):
do if val[x] * p(x, y) > val[y]:
val[y] = val[x] * p(x, y)
I've changed the sign to >
, since you want the probability to be as large as possible.
Logs are helpful because (1) log(xy) = log(x) + log(y)
(as you said) and sums are easier to compute than products, and (2) log(x)
is a monotonic function of x
, so log(x)
and x
have their maximum in the same place. Therefore, you can deal with the logarithm of the probability, instead of the probability itself:
do if log_val[x] + log(p(x, y)) > log_val[y]:
log_val[y] = log_val[x] + log(p(x, y))
Edited to add (since I don't have enough rep to leave a comment): you'll want to initialize your val
array to 0
, rather than Infinity
, because you're calculating a maximum instead of a minimum. (Since you want the largest probability of not failing.) So, after log transforming, the initial log_val
array values should be -Infinity
.