4
$\begingroup$

In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

This will not work. Consider

  • (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.

$\endgroup$
2
  • $\begingroup$ but for dijkstra, it will also consider the path after exploring a - b - d since the algorithm stores all the node inside the queue first. Then the maximum path will be updated and we will get the correct solution? $\endgroup$ Commented Oct 13, 2019 at 20:02
  • $\begingroup$ In traditional shortest-path Dijkstra, the algorithm stops once the target node is visited for the first time. If you apply Dijkstra but simply change min to max heap, the algorithm will terminate once you visit (d), but you will not (necessarily) find the max cost path. $\endgroup$
    – badroit
    Commented Oct 13, 2019 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.