Re: Finding longest path between two vertices

On Mon, 18 Jun 2007 21:00:40 +0200, <tchow@xxxxxxxxxxxxx> wrote:

In article <op.tt4oy5jift6h9m@xrousse>,
Jym <Jean-Yves.Moyen+news@xxxxxxxxxxxx> wrote:
Typically, if one takes a graph with weight -1 on each edge and search for
the shortest path between two vertices, why won't that gives an
Hamiltonian path ?

It will. However, the subtle point here is that the usual algorithms that
people use for "shortest path" won't work. If you read the fine print, you
will see that Dijkstra and Bellman-Ford, for example, won't work properly in
this case. So it's probably misguided to think about the problem this way;
one should just face up to the fact that the problem is qualitatively
different from shortest-path problems with nonnegative weights, and deal
with it head-on.

I still don't get it :-(

Bellman-Ford also works with negative weights, has long as there is no cycle of negative weight (which will probably not be the case if all weights are -1, of course).

Obviously, the original problem of the OP (finding longest path) is also somewhat ill-defined if there are cycles (it will be +\infty).

Why won't Bellman-Ford algorithm work with all weights -1 (apart from cycles) ?

It should work for longest path (in a graph without cycles).

I agree that there is a problem for finding "longest simple path" (ie without taking the same edge several times). The OP had not make it clear if that's really what he meant by "longest path".

--
Hypocoristiquement,
Jym.
.

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 ... somewhat ill-defined if there are cycles. ... It should work for longest path. ...
    (comp.theory)
  • 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: Shortest Path Problem
    ... > running Dijsktra on it. ... > a shortest path weight-wise and also a shortest ... and one by sum of edge weights, ...
    (comp.theory)
  • Re: Finding longest path 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 ...
    (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)