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?

Inviting

@Kristo, can you please have a look? – Inviting

Answer 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.

Deguzman

amit, this is what I was talking about in my question. I think Longest Path problem is different from Single sourced Longest Path problem. In Longest Path problem, we need to find the single longest path in the whole graph. But in my question above, single sourced means we are given a vertex S, then find out which path is longest oriented from S. They are different problems, right? – Inviting

ah, ok, I think I made a mistake. If single sourced longest path problem can be solved, then we just for each vertex we do single-source longest path, then compare them all, then solve the longest path problem. This is not possible as the longest path problem is NP. ok, I guess what I thought wrong. – Inviting

can you please possibly use simplest words to describe why longest path problem can't be solved if I replace MIN with MAX in Dijkstra? – Inviting

@JacksonTale: The idea behind dijkstra's algorithm is doing local relaxation. Note that in dijkstra's algorithm, when a node with minimal distance is picked and removed from the list of nodes, it is OK, we will never need to modify it again, while for the max problem - it is not true. – Deguzman

@Evgeny Kluev's answer is totally different. who I should trust? :D – Inviting

@JacksonTale: Evgeny's answer makes different assumption then stated in the question. If you can control the input to have only negative weights - Evgeny's answer is correct, there is a simple reduction to shortest weight problem. However, if the input is as stated in the question - no negative weights, the problem is NP-Hard. – Deguzman

Yeah I also commented on his answer. Thanks for answering my answer for the 3rd time. I am self learning algorithms and will put every excise I can't solve in stackoverflow, lol, this is my plan. Hope you can help me further in the future. – Inviting

what if the graph is DAG with all positive edges? or a AG with all positive edges? – Inviting

@JacksonTale in DAG there are at most O(n^2) paths, so this problem is much easier then the general case, and could be solved polynomially. – Deguzman

Can I use or modify Dijkstra, I mean for DAG with all positive edges – Inviting

@JacksonTale: I believe a modification exist, but I cannot think of it at the moment. As you already know however, I prefer reducing problems to existing algorithms instead of modifying algorithms. In this case, I'd create a new weight function w'(e) = -w(e), and invoke Bellman Ford with w'. Since the graph is a DAG, there are no cycles, and specifically no negative cycles, and BF will return the shortest path according to w', which is the longest path according to w! What do you think? Is that fits your problem as well? – Deguzman

Yes, I think you are right and your idea of reducing problem or transforming problem is always best and I agree. – Inviting

This answer is not accurate. It is correct that in general, Dijkstra cannot be used for finding the longest path, but there is a subset of graphs for which Dijkstra can find the longest path: If all edges on the given graph G are non-positive, one can transform G to -G by negating all edges . In this case the shortest path found by Dijkstra in -G corresponds to the longest path in G – Uri

@Uri The answer is in context of the question, which asks for a general graph. Here are some more cases where it may work: (1) Only edges out of the source are negative. (2) Graph has no edges (3) graph is a tree. But the question is NOT about a special subclass of graphs, this restriction is not introduced to the question, and I saw no reason to address this specifically (and not, say, it works on trees) – Deguzman

@amit: There are two things to consider: The classic shortest path Dijkstra algorithm only works on graphs with non-negative edges, not all graphs, so the problem is not general to begin with. Similarly, one can use Dijkstra for finding the longest path by using -G for graphs with non-positive edges. So the two cases are symmetrical and comparable. Secondly, finding the longest path is not actually NP-Complete. What is famously known as NP-complete is finding the simple shortest path which has created a lot of confusion: https://mcmap.net/q/751880/-why-finding-the-longest-path-in-a-graph-is-np-hard – Uri

Non simple longest path is not defined, similar to BF negative cycle, if you have a positive cycle, you can do "one more loop" and get a longer path between two points. – Deguzman

Answer 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.

Tressatressia

I think your answer is doing a trick. If I assume only negative weights, the longest path is like shortest path in all positive weights. I don't think it is what the excise is seeking for. – Inviting

@JacksonTale, yes, this is just a trick. But it's not clear from the excise text, what does it mean. Otherwise, amit's answer is very good. – Tressatressia

Thanks for answering. I guess what the excise really mean is for the real longest path problem. My bad to add such an assumption. – Inviting

The idea of using Dijkstra's for non-positive weights is very interesting. Especially, when we're required to find longest path for a graph G with all edges of -ve or zero weights, then it's wiser to apply Dijkstra's rather than Bellman-Ford's on the transformed grapgh G' =(-G) in order to achieve better run-time. – Musk

Answer 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

Translative

Also doesn't work in DAG's, as explained in amit's answer. – Misrule