From: "A.Dragojevic" <dral@sezampro.yu>
Subject: Re: Can Dijkstra's Shortest Path Algorithm solve longest path problems??
Date: Fri, 28 Apr 2000 04:39:06 +0200
Newsgroups: sci.math.research

You may try the Floyd's algorithm.
Alex.
George Russell <ger@Informatik.Uni-Bremen.DE> wrote in message
news:38FC2978.C42C0D31@informatik.uni-bremen.de...
> > [ 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.
>