Re: Shortest path with a different norm from conventional

[Vladimir Chukharev]

On Friday, March 15, 2013 8:19:28 PM UTC+2, N3wbi3 wrote:

Let's call A B C D the nodes of the shortest path.

edges between each node have a property (let's call it "rate" so "r")

A-B rAB=1.2

B-C rBC=1.3

C-D rCD=1.1

Distance between A and D is: rAB * rBC * rCD (and not plus)

Did you think about using log(r) as the property, and convert back only when needed?

Quite often this works well...

[Federico Vaggi]

Hi,

Finding the longest paths in a network is an NP complete problem, and not actually very easy to solve, except using heuristics.  

http://en.wikipedia.org/wiki/Longest_path_problem

I don't think the fact that you look for a product, instead of an addition will make things any easier.  What I'd suggest is finding a transformation (for example, the log transform suggested) that will allow you to look for shortest paths instead of longest paths.

Federico

On Friday, 15 March 2013 19:19:28 UTC+1, N3wbi3 wrote:

Hello,

I'm beginner with graph theory.

and this is the first time I'm trying to use NetworkX...

but I know Python quite well.

I'm using a MultiGraph to model my problem.

I would like to determine shortest path between two nodes...

I will give you a sample to explain the "special norm" I'm looking for...

Let's call A B C D the nodes of the shortest path.

edges between each node have a property (let's call it "rate" so "r")

A-B rAB=1.2

B-C rBC=1.3

C-D rCD=1.1

Distance between A and D is: rAB * rBC * rCD (and not plus)

What I call shortest path... is in fact "maximum" distance

I want to find the path to get the bigger number for product of rates

(and not adding distance)

I don't know how to tackle this problem...

I hope someone here can help me.

Kind regards

N3wbi3

PS : I ever have some python code to define my problem

and I also output a dot file to draw my MultiGraph with GraphViz

[Dan Schult]

To sue shortest path where edge weights should be multiplied you can change the weights to log of their original value and the sum the log weights. (Aric mentioned this).

If the log weights are "nice" you can switch your weights using new_weight = 1/old_weight.

Then the shortest path might be what you mean by "maximum distance".  

Combining these two, set the new weights to  1/log(original weights)

Lots of "tricks" can be played with weights.

:)

Dan

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.