[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/>