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

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.

Answer 2

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.

Answer 3

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

Answer 4

I suggest you modify the Dijkstra's algorithm to take the inverted value of the edge weight. Because the graph is acyclic, the algorithm will not enter an endless loop, using the negative weights to keep optimising. What is more, now positive weights become negative, but, again, there are no cycles. This will work even if the graph is undirected, provided that you disallow reinsertion of visited nodes (i.e., stop the endless jumping between two nodes, because adding negative value will always be better).

Answer 5

The answer is YES it is possible.

The Dijkstra algorithm finds the shortest path in a graph. So if you want to modify this algorithm to find the longest path in a graph, then you just have to multiply the edge weight by "-1". With this change the shortest path will be actualy the longest path.

If you want to extract the result, just multiply the result by "-1".

Here is an example:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Longest_Path
{
public static class Program
{
    public static void Main(string[] args)
    {
        var nodesCount = int.Parse(Console.ReadLine());
        var edgesCount = int.Parse(Console.ReadLine());

        var graph = new List<Edge>[nodesCount + 1];

        var comesFrom = new int[nodesCount + 1];
        var nodesTime = new double[nodesCount + 1];
        for (int i = 0; i <= nodesCount; i++)
        {
            comesFrom[i] = -1;
            nodesTime[i] = double.PositiveInfinity;
        }

        for (int i = 0; i < edgesCount; i++)
        {
            var input = Console.ReadLine().Split();

            var from = int.Parse(input[0]);
            var to = int.Parse(input[1]);
            var weight = double.Parse(input[2]);

            var edge = new Edge(from, to, weight * -1);

            if (graph[from] == null)
            {
                graph[from] = new List<Edge>();
            }

            if (graph[to] == null)
            {
                graph[to] = new List<Edge>();
            }

            graph[from].Add(edge);
        }

        var source = int.Parse(Console.ReadLine());
        var destination = int.Parse(Console.ReadLine());

        nodesTime[source] = 0;

        var priorityQueue = new Queue<int>();
        priorityQueue.Enqueue(source);

        while (priorityQueue.Any())
        {
            var fastestNode = priorityQueue.Dequeue();

            foreach (var child in graph[fastestNode])
            {
                if (!priorityQueue.Contains(child.to))
                {
                    priorityQueue.Enqueue(child.to);
                }

                var currentTime = nodesTime[child.from] + child.weight;
                if (currentTime < nodesTime[child.to])
                {
                    nodesTime[child.to] = currentTime;
                    comesFrom[child.to] = child.from;
                }
            }

            priorityQueue = new Queue<int>(priorityQueue.OrderBy(x => nodesTime[x]));
        }

        Console.WriteLine(nodesTime[destination] * -1);

        var path = new Stack<int>();
        path.Push(destination);
        var currentNode = destination;

        while (comesFrom[currentNode] != -1)
        {
            currentNode = comesFrom[currentNode];
            path.Push(currentNode);
        }

        Console.WriteLine(string.Join(' ', path));
    }
}

public class Edge
{
    public readonly int from;
    public readonly int to;
    public readonly double weight;
    public Edge(int firstNode, int secondNode, double weight)
    {
        this.from = firstNode;
        this.to = secondNode;
        this.weight = weight;
    }
}

}

Answer 6

Not enough reputation to comment on @punkyduck's answer, but I'd like to mention that replacing min with max in the DAG

a ——2——→ b ——2——→ c
│                 ↑
│                 │
1                 4
│                 │
└——————→ d ———————┘

actually works, as the algorithm will

• first examine a ⇨ ab=2, ad=1 ⇨ l(b)=(ab,2), l(d)=(ad,1)
• then examine b since we use max ⇨ abc=2 ⇨ l(c)=(abc,2)
• then examine c since abc>ad ⇨ Nothing happens
• at last examine d ⇨ adc=5 ⇨ update l(c)=(adc,5)

So at the last step the correct longest path adc is found. Just to point out the mistake.

Answer 7

The only requirement is not to have negative cycles. If you don't have the cycles, then you can remap negative ones by adding the highest absolute value from the negative weights to all the weights. That way you will lose the negative wights, as all the weight will be equal or grater than zero. So too sum up the only thing to worry is not having a negative cycle.