Re: Finding longest path in graph between two vertices

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.

What's the definition of longest path if there
is a cycle?

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?

Barring cycles, I suspect that you may be able to
use a shortest-path algorithm this way but you'd have
to look at the algorithms in detail to see if something
in them assumes positive weights.

- Randy

.

Relevant Pages