6
$\begingroup$

Is it possible to modify Dijkstra´s algorithm in order to get the longest path from $s$ to $t$ ?.

My intuition says that I´ll need a different algorithm entirely. Finding the longest path is the same as finding the shortest path on a graph with negative weights. However, Dijkstra’s algorithm requires that the weights are positive, so it cannot be modified to calculate the longest path. A better algorithm to use could be: http://en.wikipedia.org/wiki/Longest_path_problem

Any idea of how to modify it?

Improve this question
$\endgroup$
4
  • $\begingroup$ Please try to do some research before asking here. You already found a Wikipedia page that explains that "the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP". (This is a direct quote from the very first paragraph of the page you linked to.) Sounds like you've already found the answer to your own question at the very page you linked to. Also, if you'd used search on this site before asking, you would have found the following question, which explains that your problem is NP-complete: cs.stackexchange.com/q/10732/755 $\endgroup$
    – D.W. ♦
    Commented Nov 13, 2013 at 17:53
  • $\begingroup$ Please try to read well the question before posting. I´ve never write a such thing about "polynomial time". I just want to modify the algorithm. I dont care if it is not "optimum" $\endgroup$
    – winston smith
    Commented Nov 14, 2013 at 1:53
  • $\begingroup$ winston, I certainly did read the question. It's your responsibility to demonstrate what research you've done, and to describe your requirements. If you don't require your algorithm to be efficient enough that it will complete within your lifetime on medium-sized problem instances (e.g., if you don't require a polynomial-time solution), that is unusual enough that I would advise you to state it explicitly in the question. I can't read your mind. $\endgroup$
    – D.W. ♦
    Commented Nov 14, 2013 at 5:47
  • $\begingroup$ cs.stackexchange.com/q/74406/755 $\endgroup$
    – D.W. ♦
    Commented Jun 14, 2021 at 5:45

2 Answers 2

Reset to default
6
$\begingroup$

Longest path is basically the Hamiltonian Cycle problem or the Traveling Salesman Problem, and it is NP-hard. So no, and if you find a way, then ${\rm \mathbf{P=NP}}$.

The existence or non-existence of an algorithm to find the largest path, in polynomial time, is essentially part of the largest open problem in all of CS (and probably in math).

Incidentally, the Bellman–Ford algorithm can handle negative weights, so long as they don't form a cycle; in which case, if it encounters one (ie. if the cycle is reachable from the source), it would run forever, running 'round and 'round the cycle, accumulating a "shorter" and "shorter" path. Of course, it can detect this, and terminate, and is thus useful for detecting such cycles.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Finding the longest path is hard for general graphs, but you can find it in polynomial time for some special classes of graphs, such as block graphs which generalize trees. $\endgroup$
    – Juho
    Commented Nov 13, 2013 at 10:44
  • $\begingroup$ @Juho also a DAG $\endgroup$
    – Realz Slaw
    Commented Nov 13, 2013 at 10:45
  • 1
    $\begingroup$ I don't understand how the longest path is the same thing as HC or TSP. Bellman-Ford you mentioned is exactly the algorithm that can find the path if you invert the edge lengths. If there's a reachable negative cycle, then there is no longest path and this condition will be detected. You might be correct if the OP wanted to find the longest simple path, but I don't think that's what they want. $\endgroup$
    – avakar
    Commented Nov 13, 2013 at 10:49
  • 1
    $\begingroup$ @avakar well, he essentially linked longest path problem ... that sort of clears up the ambiguity. But you might be right, in that the OP doesn't know what the OP wants, in which case he should indeed investigate the Bellman-Ford algorithm. $\endgroup$
    – Realz Slaw
    Commented Nov 13, 2013 at 10:54
  • 1
    $\begingroup$ Why do people always think of the longest path problem as "the longest path in the entire graph" rather than "single source longest path" and simply dismiss it NP-Hard? $\endgroup$
    – Paghillect
    Commented Apr 24, 2018 at 6:46
0
$\begingroup$

"sort-of-yes". there is a fairly natural modification to the algorithm to scan through the "frontier edges" by adding to the current spanning tree the longest 1st (by weight) instead of the shortest 1st. this will not result in the longest path, but it is a greedy-type algorithm that will result in a "longish" path. have not seen this variant/heuristic studied. it would be interesting to measure how close it comes to the optimum.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ It won't be too good; for directed graphs, the problem is known to be hard to approximate within $n^{1-\epsilon}$ for any $\epsilon > 0$ unless $P=NP$. Further assuming SAT can't be solved in subexponential time, there is no polytime algorithm for finding a directed path of length $\Omega(f(n)\log^2n)$ for any nondecreasing polynomial time computable function $f$ in $\omega(1)$. $\endgroup$
    – Juho
    Commented Nov 14, 2013 at 15:14
  • $\begingroup$ thx for the detailed bounds. questioner did not insist on directed graphs. wonder about undirected case also. better possible bounds/performance? in any case the idea of greedy algorithms variants/heuristics may work acceptably well on some real-world/average case instances. $\endgroup$
    – vzn
    Commented Nov 14, 2013 at 16:05
  • $\begingroup$ AFAIK, we don't know as much about the undirected case (I think the references listed on Wikipedia on it have the latest). $\endgroup$
    – Juho
    Commented Nov 14, 2013 at 16:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.