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$
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Jienan Tang Oct 13 '19 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 Oct 13 '19 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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