Dijkstra for longest path in a DAG

There're three possible ways to apply Dijkstra, NONE of them will work:
1.Directly use “max” operations instead of “min” operations.
2.Convert all positive weights to be negative. Then find the shortest path.
3.Give a very large positive number M. If the weight of an edge is w, now M-w is used to replace w. Then find the shortest path.

For DAG, critical path method will work:
1: Find a topological ordering.
2: Find the critical path.
see [Horowitz 1995] E. Howowitz, S. Sahni and D. Metha, Fundamentals of Data Structures in C++, Computer Science Press, New York, 1995

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:

1. The graph is not only directed acyclic, but also acyclic if you remove the directions. In other words: It is a tree. Because in a tree the longest path is also the shortest path.
2. The graph has only negative weights. Then you can use max instead of min to find the longest path. BUT this works only if the weights are really negative. If you just invert positive weights it will not work.

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.