Re: Finding longest path between two vertices

On Jun 18, 3:36 pm, Jym <Jean-Yves.Moyen+n...@xxxxxxxxxxxx> wrote:
On Mon, 18 Jun 2007 21:00:40 +0200, <t...@xxxxxxxxxxxxx> wrote:
In article <op.tt4oy5jift6h9m@xrousse>,
Jym <Jean-Yves.Moyen+n...@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.

Right, Bellman-Ford works in directed graphs with no negative cycles.

Note that if the graph is acyclic, you can compute shortest/longest
path in linear time via topological sort.


.

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
    ... 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
    ... who will assign edge weights to the ... 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? ... Negating the weights and looking for shortest path seems alright with me. ...
    (comp.theory)