Re: Finding longest path between two vertices

Thanks for the correction and sorry for posting wrong information.
I did not think enough about my solution (it just seemed so (too?)
easy), because I was short in time.

Tobias

On Fri, 15 Jun 2007 10:29:13 +0200
Robby Goetschalckx <robby@xxxxxxxxxxxxxxxxx> wrote:

Tobias Columbus wrote:
Hallo

Instead of negating the weights w you may try 1/w (all weights are
positive you said) and then you can run Dijkstras algorithm finding
the shortest path which should be longest path with weights w

Hope this helps you
Tobias


This is not correct. Consider a simple graph with two possible paths
of the start-node to the goal-node:
* one consisting of a single edge with weight 2
* one consisting of two edges, both with weight 2

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 ...

robby
.

Relevant Pages

  • Re: SNe1a data
    ... > the data is shown with k correction whereas in the tables ... In the simplest case, which is probably good enough here, the weight ... that the uncertainties are Gaussian and correct. ... > readings compared to the expected dilated template values.. ...
    (sci.astro)
  • Correction on Vehicle Weight - Newcomer Advice on Which Caravan
    ... Correction to the details given in my initial mail. ... The vehicle weight, ... We have just decided to get into touring with a caravan but don't really ... correctly is around 1,500 Kg in weight. ...
    (uk.rec.caravanning)
  • Re: Finding longest path between two vertices
    ... one consisting of a single edge with weight 2 ... one consisting of two edges, both with weight 2 ... 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 ... ...
    (comp.theory)
  • Re: Finding longest path between two vertices
    ... After transforming to 1/w, the first path has a new weight of 0.5, and ... first path in the original graph should be longer ... ...
    (comp.theory)
Loading