I am trying to find out if it is possible to use Dijkstra's algorithm to find the longest path in a directed acyclic path. I know that it is not possible to find the longest path with Dijkstra in a general graph, because of negative cost cycles. But it should work in a DAG, I think. Through Google I found a lot of conflicting sources. Some say it works in a dag and some say it does not work, but I didn't find a proof or a counter example. Can someone point me to a proof or a counter example?
I thought about the problem and I think it is not possible in general. Being acyclic is not enough, I think.
For example:
We want to go from a to c in this dag.
a - > b - > c
| /\
v |
d - - - - -
d-c has length 4
a-d has length 1
all others have length 2
If you just replace the min function with a max function, the algorithm will lead to a-b-c but the longest path is a-d-c.
I found two special cases where you can use Dijkstra for calculating the longest path: