Re: Finding longest path between two vertices

In article <5db77cF3356h4U1@xxxxxxxxxxxxxxxxxx>,
Tim Frink <plfriko@xxxxxxxx> wrote:
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.

In general this is NP-hard, because the longest possible path is a
Hamiltonian path, if a Hamiltonian path exists.

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's Algorithm (due to the weight negation it should find not
the shortest but longest path).

I'm not sure what you're trying to do in (a), but (b) won't work because of
negative cycles.

Or do you know any faster approach?

Try taking a look at
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE176.HTM
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.