Re: Finding longest path between two vertices

On Mon, 18 Jun 2007 07:31:59 +0200, Joachim Pimiskern <JoachimPimiskern@xxxxxx> wrote:

Tim Frink schrieb:
> Do you see any problems with my suggestion of negating
> the edge weights and than search the shortest path?

It's not you, who will assign edge weights to the
original graph, it's the user of your algorithm.
To get a Hamiltonian path, he'll set all edges
to the same value, e.g. 1.

Well, I'm not completely sure with the argument (erm, the fact that Tim Chow support it make me think that I have missed the point)...

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 ?

If weights -1 everywhere doesn't give Hamiltonian path, how comes weights 1 and longest path gives it ?

Negating the weights and looking for shortest path (or, rather, modyfing directly the algorithm) seems alright with me.

--
Hypocoristiquement,
Jym.
.

Relevant Pages

  • 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
    ... 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 between two vertices
    ... at least if the algorithm is able to handle negative ... You always have to beware of loops, but in the case of loops ... there is no problem with negating the edge weights and then ...
    (comp.theory)
  • Re: Finding longest path between two vertices
    ... > Do you see any problems with my suggestion of negating ... > the edge weights and than search the shortest path? ... who will assign edge weights to the ...
    (comp.theory)