Re: Finding longest path between two vertices

Tim Frink wrote:
On Fri, 15 Jun 2007 10:29:13 +0200, Robby Goetschalckx wrote:


After transforming to 1/w, the first path has a new weight of 0.5, and the second a weight of 0.5 + 0.5, so according to your assumption the first path in the original graph should be longer ...


Do you see any problems with my suggestion of negating the edge weights
and than search the shortest path?

Tim


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.

robby
.

Relevant Pages

  • 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: RBF Interpolation
    ... Why I could get some negative weights? ... shrinks the support of the gaussian to essentially a single point, ... I need to interpolate a 3D particle ...
    (sci.math.num-analysis)
  • Re: RBF Interpolation
    ... Is there anybody worked on RBF interpolate the scattering data point ... Why I could get some negative weights? ... shrinks the support of the gaussian to essentially a single point, ...
    (sci.math.num-analysis)
  • Re: Wvg function
    ... design averages. ... Where "a" is an array of elements and w is ... Why do you need two loops to calculate an average ... Where are your weights ...
    (comp.lang.c)