Re: Finding longest path in graph between two vertices
- From: Tim Frink <plfriko@xxxxxxxx>
- Date: Thu, 14 Jun 2007 10:06:54 +0200
On Wed, 13 Jun 2007 23:13:19 +0000, gowan4@xxxxxxxxxxx wrote:
On Jun 13, 5: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?
Thank you.
Tim
The dynamic programming approach makes no assumptions about the
weights.
Yes, I know that dynamic programming would be one way to solve the
longest-path problem. But for a more complex graph the formulation
of the problem with all it's constraints is too extensive. Or do you
think this is the only sensible approach and one should spend some time
to automatize it.
.
- References:
- Finding longest path in graph between two vertices
- From: Tim Frink
- Re: Finding longest path in graph between two vertices
- From: gowan4@xxxxxxxxxxx
- Finding longest path in graph between two vertices
- Prev by Date: Re: Finding longest path in graph between two vertices
- Next by Date: Re: Finding longest path in graph between two vertices
- 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
|
