Dijkstra for longest path in a DAG

by

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.

More Related Contents:

  1. Dijkstra’s algorithm with negative weights
  2. Dijkstra Program
  3. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  4. Negative weights using Dijkstra’s Algorithm
  5. Find the shortest path in a graph which visits certain nodes
  6. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  7. Dijkstra Shortest Path with VertexList = ListS in boost graph
  8. How does Dijkstra’s Algorithm and A-Star compare?
  9. Find cycle of shortest length in a directed graph with positive weights
  10. graph – Dijkstra for The Single-Source Longest Path
  11. Why does Dijkstra’s algorithm use decrease-key?
  12. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1

Leave a Comment