# Can you use Dijkstra's algorithm to find the maximum cost path?

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?

• (I wouldn't mind if you checked the title for typos.) Aug 26, 2021 at 7:15
• (Some mind exercise. Then again, you could find the maximal initial cost $IC$ and use as cost $c_i = IC - ic_i + 1$.) Aug 26, 2021 at 7:19
• Aug 26, 2021 at 20:32

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.