Graph Theory37 sections · 1633 units
Open in CourseQuiz: Dijkstra Modifications
Knowledge check
Check Your Understanding
In the Maximum Probability problem, edge weights are probabilities between and . You want to maximize the product of probabilities along a path. How do you adapt Dijkstra for this?
- A.Negate all weights and find the shortest path
- B.Use a max-heap instead of a min-heap and update with multiplication instead of addition
- C.Convert probabilities to integers by multiplying by
- D.Run Dijkstra normally. It works with probabilities without changes