Dijkstra for longest path in a DAG

Question

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?

Answer 1

Longest distance problem has no optimal substructure for any graph, DAG or not. However, any longest distance problem on graph G is equivalent to a shortest distance problem in a transformed graph G'=-G i.e. sign of each edge weight is reversed.

If the transformed graph G' is expected to have negative edges and cycles, then Bellman-Ford algorithm is used for finding shortest distance. However, if G is guaranteed to have only non-negative weights (i.e. G' is non-positive weights) then Dijkstra's algorithm could be better choice over Bellman-Ford. (see 'Evgeny Kluev' response for graph - Dijkstra for The Single-Source Longest Path) If the G is a DAG, then G' will be a DAG too. For DAG, we've better algorithm for finding shortest distance and that should be chosen over Dijkstra's or Bellman-Ford's.

Summary:
Longest path problem has no optimal substructure and thus modifying min-weight function in Dijkstra's algorithm to max-weight function alone won't work for a graph, be it DAG or not. Instead of modifying any shortest-path-algorithm (well in a trivial way), we rather transform the G, and see which shortest path algorithm works best on the transformed G.

Note

     A-------B
     |       |              assume: edges A-B, B-C, C-A of same weight
     |       |
     +-------C

We see MAX_DIS(A,B)= A->C->B
For "MAX_DIS" to be optimal structure, in the above case, the relation

    MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied.

But it is not as we see, MAX_DIS(A,C)=A->B->C and MAX_DIS(C,B)= C->A->B and thus it provides an example that longest distance problem may not have optimal sub-structure.