Re: Finding longest path between two vertices

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: >^..^< Starting the K/D diet
    ... consisting of some dry cereal and half a cantaloupe. ... easy for me to simply have one meal a day, no snacks or fruit juices. ... My weight is also stable, even though I don't eat much and typically ...
    (rec.arts.sf.fandom)
  • Re: Finding longest path between two vertices
    ... Thanks for the correction and sorry for posting wrong information. ... one consisting of a single edge with weight 2 ... both with weight 2 ... After transforming to 1/w, the first path has a new weight of 0.5, ...
    (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)