Re: Finding longest path between two vertices

Hallo

Instead of negating the weights w you may try 1/w (all weights are
positive you said) and then you can run Dijkstras algorithm finding the
shortest path which should be longest path with weights w

Hope this helps you
Tobias

On Jun 13, 9:51 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's 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?

There is an efficient approach for finding the longest paths for
acyclic digraphs. If you allow cycles, the longest path as you have
defined it (or not defined it) is infinite.

Brett


Thank you.

Tim


.

Relevant Pages

  • Re: Finding longest path between two vertices
    ... people use for "shortest path" won't work. ... Bellman-Ford also works with negative weights, has long as there is no cycle of negative weight. ... Why won't Bellman-Ford algorithm work with all weights -1 (apart from cycles)? ... It should work for longest path. ...
    (comp.theory)
  • Re: Finding longest path between two vertices
    ... people use for "shortest path" won't work. ... Bellman-Ford also works with negative weights, has long as there is no ... somewhat ill-defined if there are cycles. ... It should work for longest path. ...
    (comp.theory)
  • Re: Finding longest path in graph between two vertices
    ... I have a directed graph with weighted edges (weights are all positive). ... I'm looking for an efficient algorithm to find the longest path ...
    (sci.math)
  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • RE: [REPORT] cfs-v4 vs sd-0.44
    ... The definition for proportional fairness assumes that each thread has a ... threads have fixed weights throughout the interval. ... approximate this ideal scheduler (often referred to as Generalized ... The goal of a proportional-share scheduling algorithm is to minimize the ...
    (Linux-Kernel)