2
$\begingroup$

Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree.

Is it possible to negate all the weights and then apply Dijkstra's algorithm on the negative weights? All the paths here will have a negative weight, but in this situation, I think Dijkstra's algorithm would still work?

Alternatively, could you apply Dijkstra's algorithm to the original positive weights, but instead of a min heap you use a max heap?

$\endgroup$
3
  • $\begingroup$ (I wouldn't mind if you checked the title for typos.) $\endgroup$
    – greybeard
    Aug 26, 2021 at 7:15
  • $\begingroup$ (Some mind exercise. Then again, you could find the maximal initial cost $IC$ and use as cost $c_i = IC - ic_i + 1$.) $\endgroup$
    – greybeard
    Aug 26, 2021 at 7:19
  • $\begingroup$ Related: Dijkstra for longest path in a DAG $\endgroup$ Aug 26, 2021 at 20:32

2 Answers 2

3
$\begingroup$

No, Dijkstra's algorithm will not work. Consider the following counter-example: $V = \{s,u,t\}$ and $E = \{(s,u),(u,t)(s,t)\}$. The weights on the edges is as follows: $w(s,u) = 1$, $w(u,t) = 3$, and $w(s,t) = 2$.

Here the Dijkstra's algorithm with negative weights would give the shortest path $(s,t)$. However, the shortest path is $s$->$u$->$t$, which is the longest path in the positively weighted graph.

$\endgroup$
2
  • $\begingroup$ Ah I see, but what if we modify Dijkstra's algorithm so that it doesn't terminate when reaching the end point? And just let it keep going until all nodes are popped out of the priority queue? $\endgroup$
    – David
    Aug 26, 2021 at 14:03
  • $\begingroup$ @David Not sure about it. Maybe you can write a separate question explaining the modified algorithm. It will also give you clarity and it would be a fruitful discussion afterward. $\endgroup$ Aug 26, 2021 at 14:15
0
$\begingroup$

Note that, Dijkstra can't compute optimal shortest path when there are negative weights. So when you negate weights, the longest path will be shortest path, but Dijkstra can't find that.

$\endgroup$

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.