[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ns] longest-path algo??
On Sat, 24 Nov 2001, Sivakumar B wrote:
> The same Dijkstras Algo can be accordingly modified to find the longest
> path. It should be equally efficient as finding the shortest path.
you mean longest non-looping path, right? If there are loops, how will
the algorithm converge on a result?
I don't see how the relaxation process can be easily reworked for a
longest path, because a longer path will require checking for cases
that do not go through the already-selected node u.
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
L.
and performance should be a lot worse, once modified to work.
> > Anyone know any algorithm which finds the longest path between two
> >nodes(just like dijkstra's shortest path algorithm). If so, please let me
> >know.
> >
<L.Wood@surrey.ac.uk>PGP<http://www.ee.surrey.ac.uk/Personal/L.Wood/>