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.

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.

.

Relevant Pages