If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)

Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Longest Path Problem

djpbarry · 2007-11-30 14:24:25

Hi guys Is anyone aware of any algorithms for finding the longest connected path within a graph? I am aware of algorithms for the opposite problem (Dijkstra's algorithm), but there seems to be little out there for my purposes.

Options

30-11-2007 3:24pm

#1

djpbarry

Registered Users Posts: 13,104 ✭✭✭✭

Join Date: June 2006

Posts: 12697

Hi guys

Is anyone aware of any algorithms for finding the longest connected path within a graph?

I am aware of algorithms for the opposite problem (Dijkstra's algorithm), but there seems to be little out there for my purposes.

0

Comments

Options
#2 30-11-2007 6:15pm
Webmonkey

Registered Users Posts: 9,579 ✭✭✭

Join Date: March 2003

Posts: 9397

Have a look at this:

http://forum.java.sun.com/thread.jspa?threadID=326538&messageID=1325792

0
Options
#3 30-11-2007 6:19pm
rmacm

Closed Accounts Posts: 2,039 ✭✭✭

Join Date: July 2003

Posts: 1967

This may be of some help.....I googled and got some hits.

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE176.HTM

0
Options
#4 01-12-2007 9:01am
ravydavygravy

Registered Users Posts: 545 ✭✭✭

Join Date: June 2004

Posts: 495

Isn't longest path NP-Complete (in general)? Thought I remembered this from CS.
Google seems to think so also: http://www.google.ie/search?q=longest+path+np+complete

Are there any specific restrictions on your problem that might make it solvable?

0