Re: Finding longest path in graph between two vertices
- From: galathaea <galathaea@xxxxxxxxx>
- Date: Wed, 13 Jun 2007 17:33:18 -0700
On Jun 13, 2:52 pm, Tim Frink <plfr...@xxxxxxxx> wrote:
Hi,
I have a directed graph with weighted edges (weights are all positive).
Now, I'm looking for an efficient algorithm to find the longest path
between two given vertices.
My idea was to negate all edge weights and than to run
a) a topological sort and than a relaxation to find the critical path
or
b) Bellman-Ford Algorithm (due to the weight negation it should find not
the shortest but longest path).
Are these algorithms suited for the longest-path problem? And if so,
which one is more efficient?
Or do you know any faster approach?
others have given very good advice
but i just wanted to answer your specific questions
a) relaxation is not guaranteed to give you the minimum
but can regularly come pretty close quickly
a topological sort with exhaustive search will guarantee
but returns you to the NP-hard times mentioned elsewhere
b) bellman-ford is only applicable if you have
no negative total weight cycles
if you want to allow such cycles
you must add rules to the definition of path
that exclude repeatedly traversing the loop
or revisiting vertices
or whatever works for your circumstance
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
.
- Follow-Ups:
- Re: Finding longest path in graph between two vertices
- From: Tim Frink
- Re: Finding longest path in graph between two vertices
- References:
- Finding longest path in graph between two vertices
- From: Tim Frink
- Finding longest path in graph between two vertices
- Prev by Date: Re: Exponential Equation (with sum)
- Next by Date: Re: Separation,Power and Countability.
- Previous by thread: Re: Finding longest path in graph between two vertices
- Next by thread: Re: Finding longest path in graph between two vertices
- Index(es):
Relevant Pages
|
