graph - Dijkstra for The Single-Source Longest Path

Question

Ok, I posted this question because of this exercise:

Can we modify Dijkstra’s algorithm to solve the single-source longest path problem by changing minimum to maximum? If so, then prove your algorithm correct. If not, then provide a counterexample.

For this exercise or all things related to Dijkstra's algorithm, I assume there are no negative weights in the graph. Otherwise, it makes not much sense, as even for shortest path problem, Dijkstra can't work properly if negative edge exists.

---

Ok, my intuition answered it for me:

Yes, I think it can be modified.

I just

1. initialise distance array to MININT
2. change distance[w] > distance[v]+weight to distance[w] < distance[v]+weight

---

Then I did some research to verify my answer. I found this post:

Longest path between from a source to certain nodes in a DAG

First I thought my answer was wrong because of the post above. But I found that maybe the answer in the post above is wrong. It mixed up The Single-Source Longest Path Problem with The Longest Path Problem.

Also in wiki of Bellman–Ford algorithm, it said correctly :

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights.

So I think my answer is correct, right? Dijkstra can really be The Single-Source Longest Path Problem and my modifications are also correct, right?

Solution 1

No, we cannot¹ - or at the very least, no polynomial reduction/modification is known - longest path problem is NP-Hard, while dijkstra runs in polynomial time!

If we can find a modfication to dijsktra to answer longest-path problem in polynomial time, we can derive P=NP

If not, then provide a counterexample.

This is very bad task. The counter example can provide a specific modification is wrong, while there could be a different modification that is OK.
The truth is we do not know if longest-path problem is solveable in polynomial time or not, but the general assumption is - it is not.

---

regarding just changing the relaxation step:

        A
       / \
      1   2
     /     \
    B<--1---C
edges are (A,B),(A,C),(C,B)

dijkstra from A will first pick B, and then B is never reachable - because it is out of the set of distances.

At the very least, one will have also to change min heap into max heap, but it will have a different counter-example why it fails.

---

(1) probably, maybe if P=NP it is possible, but it is very unlikely.

Solution 2

Yes, we can. And your answer is almost correct. Except one thing.

You assume no negative weights. In this case Dijkstra's algorithm cannot find longest path.

But if you assume only negative weights, you can easily find the longest path. To prove correctness, just take absolute values of all weights and you get exactly the usual Dijkstra's algorithm with positive weights.

Solution 3

It works in directed acyclic graphs but not in cyclic graphs. Since the path will back track and there is no way of avoiding that in dijkstra's algo