Re: Finding longest path between two vertices

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 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: Finding longest path between two vertices
    ... Instead of negating the weights w you may try 1/w (all weights are ... shortest path which should be longest path with weights w ... I'm looking for an efficient algorithm to find the 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 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: Complexity of Finding the longest simple path in a graph
    ... The reachability graph is not ... longest path w.r.t. the number of "steps" that can be made without ... height of the tree, but here it is not a tree... ... all weights are the same or should I call my problem "graph height"? ...
    (comp.theory)
  • Re: A question about Dijkstras algorithm
    ... When a directed graph contains positive cycles, the longest path is ... It can be found using Bellman algorithm: ... 1- a directed acyclic graph whose edges' weights are all positive. ...
    (comp.theory)