You can apply probabilties to your edge weights. Also, if you were considering D, consider looking at D-Lite. It's an alternate approach to the same problem, a

You can apply probabilties to your edge weights. Also, if you were considering D, consider looking at D-Lite. It's an alternate approach to the same problem, and more easily understood/implemented.