Can Dijkstra's Shortest Path Algorithm solve longest path problems??

[David]

I'm wondering, how can one convert a shortest path problem to a longest path
problems... I've tried to make each weight become its additive inverse, then
add a constant to make them all positive, but this is apparently wrong,
since for longer paths, more constants are added. I conjecture there is no
way...

[Norm Dresner]

If there is even one accessible loop in the graph then there is obviously no
"longest" path unless you exclude loops in which case I think the Dijkstra
algorithm is totally unsuitable.
Norm
David <dawenliu@_hotmail.com> wrote in message
news:8dbite$ejg$1...@gemini.ntu.edu.tw...

[Marcus Raitner]

David <dawenliu@_hotmail.com> writes:

> I'm wondering, how can one convert a shortest path problem to a longest path
> problems... I've tried to make each weight become its additive inverse, then
> add a constant to make them all positive, but this is apparently wrong,
> since for longer paths, more constants are added. I conjecture there is no
> way...
>

Your algorithm had to fail, because the LONGEST PATH problem is
known to be NP-Complete (see garey/johnson). Thus it can't be
solved by an application of Dijkstra's algorithm which is in P
(unless P=NP)

[ Moderator's note: the longest path problem in general is NP-complete,
but for acyclic directed graphs it is in P, and can be solved by
dynamical programming - in fact this is exactly what the "critical
path method" is all about.
- Robert Israel ]

Regards,

Marcus Raitner

--
--------------------------------------------------------------
Marcus Raitner
Lst. Prof. Brandenburg rai...@fmi.uni-passau.de
Uni Passau, D-94030 Passau ++49/851/509-3034, FAX: 3032

[George Russell]

> [ Moderator's note: the longest path problem in general is NP-complete,
> but for acyclic directed graphs it is in P, and can be solved by
> dynamical programming - in fact this is exactly what the "critical
> path method" is all about.
> - Robert Israel ]

To amplify that a bit, I think the situation is that you can always solve the
longest and shortest WALK problem. The difference between a walk and a path
is that you are not allowed to visit the same node more than once in a path.
Suppose for example you have an acyclic directed graph where there is no
cycle with positive sum. Then given a walk you can find a path which is as
long or longer by repeatedly removing cycles. So the longest path problem in
such a graph is solvable.

But in general, where you are trying to solve the longest path problem where
there are cycles with positive sum (or conversely the shortest path problem where
there are cycles with negative sum) finding the longest walk (respectively
shortest walk) won't do (indeed it will be infinite) won't do. Dynamic methods
don't seem to work because you have to keep track of what nodes paths have
visited in the past. And so things get NP-complete.

[A.Dragojevic]

You may try the Floyd's algorithm.
Alex.
George Russell <g...@Informatik.Uni-Bremen.DE> wrote in message
news:38FC2978...@informatik.uni-bremen.de...