Re: Finding longest path between two vertices

In article <f4u1sr$sic$1@xxxxxxxxxxxxxxxx>,
Robby Goetschalckx <robby@xxxxxxxxxxxxxxxxx> wrote:
Tim Frink wrote:
Do you see any problems with my suggestion of negating the edge weights
and than search the shortest path?

Not that I know of, at least if the algorithm is able to handle negative
weights. You always have to beware of loops, but in the case of loops
the problem is ill-defined.

Assume that a "path" by definition has no loops, so that the problem is not
ill-defined.

*Logically*, there is no problem with negating the edge weights and then
finding the path with the lowest weight.

*Algorithmically*, there is a serious problem. Dijkstra requires
nonnegative weights, and Bellman-Ford will not give the right answer if
there are cycles with total negative weight. This is not just a silly
technicality that can be fixed with an easy tweak, because as I noted
elsewhere, if you could find the longest path between two vertices then
you could in particular solve the Hamiltonian path problem.

Here again is a suggested starting point:

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE176.HTM
--
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
.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • RE: [REPORT] cfs-v4 vs sd-0.44
    ... The definition for proportional fairness assumes that each thread has a ... threads have fixed weights throughout the interval. ... approximate this ideal scheduler (often referred to as Generalized ... The goal of a proportional-share scheduling algorithm is to minimize the ...
    (Linux-Kernel)
  • Re: Compressing your levels
    ... the algorithm (with a modified function ... One should probably count the weights ... you run seam removal to remove excess portions ... another portion of the dungeon is removed? ...
    (rec.games.roguelike.development)
  • finding shortest path...
    ... G = unoriented labeled connected graph G with n vertices and maximal ... Then the edges must be labeled by random weights from ... Output of the algorithm: ... The sequential algorithm is of type BB-DFS with the search depth ...
    (comp.programming)
  • Re: how to compare between different training algorithms, to find the best algorithm???
    ... you just looking for the best algorithm to use with your ... to searching over a lot of different parameters and initial weights. ... & test set. ... answers for every trial because of random weights and biases. ...
    (comp.soft-sys.matlab)