4
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by D.W., Guy Coder, Luke Mathieson, frafl, David Richerby Nov 17 '13 at 1:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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. Nov 13 '13 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 Nov 14 '13 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. Nov 14 '13 at 5:47
5
$\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.

$\endgroup$
  • 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 Nov 13 '13 at 10:44
  • $\begingroup$ @Juho also a DAG $\endgroup$ – Realz Slaw Nov 13 '13 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 Nov 13 '13 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 Nov 13 '13 at 10:54
  • $\begingroup$ Oh, ok, sorry, never mind :) I didn't really click through to see the problem has to do with simple paths. $\endgroup$ – avakar Nov 13 '13 at 10:56
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.

$\endgroup$
  • 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 Nov 14 '13 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 Nov 14 '13 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 Nov 14 '13 at 16:24

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