patternMinor
Modifies Dijkstra’s Algorithm to find the maximum cost path
Viewed 0 times
paththedijkstramaximumalgorithmmodifiesfindcost
Problem
In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?
Solution
This will not work. Consider
Looking for the max cost path from (a) to (d), the max heap will follow (a)-4->(b)-2->(d) and never explore the (a)-1->(c) edge.
See here for an alternative based on a topological sort.
- (a)-4->(b)
- (a)-1->(c)
- (b)-2->(d)
- (c)-6->(d)
Looking for the max cost path from (a) to (d), the max heap will follow (a)-4->(b)-2->(d) and never explore the (a)-1->(c) edge.
See here for an alternative based on a topological sort.
Context
StackExchange Computer Science Q#115806, answer score: 3
Revisions (0)
No revisions yet.