Will Dijkstra work here and why?
Will Dijkstra work here and why?
In the usual Dijkstra’s algorithm you set the distance to the source initially to 0 and the distance to all other vertices to infinity, and you repeatedly select the best edge such that its weight plus the distance to its source is as small as possible.
For this problem, you set the probability to the source initially to 1 (since there is 100% probability of reaching the source without getting caught), the probability to all other vertices to 0, and repeatedly select the best edge such that its probability times the probability of reaching its source is as large as possible. All other details go as usual.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.