shortest_path with NetworkX

[Kiril Bugajev]

Hello,

I want to display a shortest path from 'a' to 'd' for the graph made of the following links and nodes:

a,c,1

c,d,1

a,b,1

b,d,1

This is the script I've developed and the result obtained:

import networkx as nx

graph = nx.Graph()

routes = open('links.txt')

for line in routes:

    orig, dest, dist = line.split(",")

    graph.add_edge(orig, dest, weight=int(dist))

print nx.shortest_path_length(graph, 'a', 'd')

print nx.shortest_path(graph, 'a', 'd')

2

['a', 'c', 'd']

I then modify the 'links.txt' file to force ['a', 'b', 'd'] to be selected as the shortest path:

a,c,10

c,d,10

a,b,1

b,d,1

However after running script again and again the old result is returned.

2

['a', 'c', 'd']

Is it possible python caches the result of previous shortest path calculations?

[Cake Erdos]

Maybe you should close the file after you print out the shortest path, i.e., routes.close()

[Kiril Bugajev]

I've actually tried that with no success. After messing around with the script I realised that result doesn't depend on the weights I define in the links.txt file.

It is always the same:

2

['a', 'c', 'd']

It looks like the weight variable is not passed on to the graph.add_edge() function and default weight of 1 is assumed for all edges.

Does anyone know why?

[Cake Erdos]

Oh, I see... You have to pass the weights of the edges to the shortest path function.

The code below should work.

Suppose the links.txt file contains the following lines.
a,c,10
c,d,9
a,b,8
b,d,7

Then the out put should be

15
['a', 'b', 'd']

import networkx as nx

graph = nx.Graph()
routes = open('links.txt')

for line in routes:
    orig, dest, dist = line.split(",")
    graph.add_edge(orig, dest, weight=int(dist))

print nx.shortest_path_length(graph, 'a', 'd',weight="weight")
print nx.shortest_path(graph, 'a', 'd',weight="weight")
routes.close()

[Kiril Bugajev]

Thank you! It is all working as expected now.