Re: Finding longest path between two vertices

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.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.