I create a digraph of 14 nodes using the Networkx module. I am getting the same output paths irrespective of changing distances when using the in-built functions.
Assume the weights are as follows for simplicity.
wei {(1, 2): 10, (1, 3): 20, (1, 8): 30, (2, 3): 40, (2, 4): 50, (3, 6): 60, (8, 7): 70, (8, 9): 80, (4, 5): 90, (4, 11): 100, (6, 5): 110, (6, 10): 120, (6, 14): 130, (5, 7): 140, (11, 12): 150, (11, 13): 160, (10, 9): 170, (14, 12): 180, (14, 13): 190, (9, 12): 200, (9, 13): 210}
Using the KSP command and the 1 shortest path command (for verification) as below I get the outputs as
list( islice(nx.shortest_simple_paths(G, 1, 2, weight='wei'), 3) ) gives
[[1, 2], [1, 3, 2], [1, 8, 7, 5, 4, 2]]
nx.shortest_path(G, source=1, target=2, weight='wei', method='dijkstra') gives
[1, 2]
which is ok since for nodes 1 to 2 the least distance is 10 units and so it is the first option.
but when I intentionally change the distance between node 1 and 2 to say 10000 using wei[(1,2)]=10000
even then, the above two commands give the same output which is wrong since an example option of [1,3,2] has distance=110.
Moreover, I observe that even when I do not give any weights i.e., weight=None, the outputs are same.
Can anyone please help with what might be going wrong here?
Additional info: I create the graph as follows
elist = [(1, 2),(1,3),(1,8),(2,3),(2,4),(3,6),(4,5),(4,11),(5,6),(5,7),(6,10),(6,14),(7,8),(8,9),(9,10),(9,12),(9,13),(11,12),(11,13),(12,14),(14,13), (2, 1),(3,1),(8,1),(3,2),(4,2),(6,3),(5,4),(11,4),(6,5),(7,5),(10,6),(14,6),(8,7),(9,8),(10,9),(12,9),(13,9),(12,11),(13,11),(14,12),(13,14)]
src_node_num=np.array([1,2,3,4,5,6,7,8,9,10,11,12,13,14])
des_node_num=np.array([1,2,3,4,5,6,7,8,9,10,11,12,13,14])
G = nx.DiGraph()
You haven't included enough information for us to know for sure, but my hunch is that you're not including wei as an edge attribute and instead are expecting networkx to look for a dictionary called wei. If this is the case, networkx currently looks for an edge-attribute called 'wei', doesn't find one, and therefore defaults to the value 1.
There are two solutions to this: either modify the graph construction to include wei as an edge attribute, or create a function that looks up the edge weight to be passed into the shortest simple paths function.
Script for option 1:
import networkx as nx
from itertools import islice
wei = {(1, 2): 10, (1, 3): 20, (1, 8): 30, (2, 3): 40, (2, 4): 50, (3, 6): 60, (8, 7): 70, (8, 9): 80, (4, 5): 90, (4, 11): 100, (6, 5): 110, (6, 10): 120, (6, 14): 130, (5, 7): 140, (11, 12): 150, (11, 13): 160, (10, 9): 170, (14, 12): 180, (14, 13): 190, (9, 12): 200, (9, 13): 210}
elist = [(1, 2),(1,3),(1,8),(2,3),(2,4),(3,6),(4,5),(4,11),(5,6),(5,7),(6,10),(6,14),(7,8),(8,9),(9,10),(9,12),(9,13),(11,12),(11,13),(12,14),(14,13), (2, 1),(3,1),(8,1),(3,2),(4,2),(6,3),(5,4),(11,4),(6,5),(7,5),(10,6),(14,6),(8,7),(9,8),(10,9),(12,9),(13,9),(12,11),(13,11),(14,12),(13,14)]
nodes = 1 + np.arange(14)
# update dist(1,2) if desired
wei[(1,2)] = 1000
# include reversed edges with same distance (so that we can look up (6,5) and (7,8))
wei.update({k[::-1]:v for k,v in wei.items()})
# build graph with "wei" as an edge attribute
G = nx.DiGraph()
G.add_nodes_from(nodes)
for edge in elist:
G.add_edge(*edge, wei = wei[edge])
list(islice(nx.shortest_simple_paths(G, 1, 2, weight='wei'),3))
The result is [[1, 3, 2], [1, 3, 6, 5, 4, 2], [1, 8, 7, 5, 4, 2]].
Script for option 2 (yields same result):
import networkx as nx
from itertools import islice
wei = {(1, 2): 10, (1, 3): 20, (1, 8): 30, (2, 3): 40, (2, 4): 50, (3, 6): 60, (8, 7): 70, (8, 9): 80, (4, 5): 90, (4, 11): 100, (6, 5): 110, (6, 10): 120, (6, 14): 130, (5, 7): 140, (11, 12): 150, (11, 13): 160, (10, 9): 170, (14, 12): 180, (14, 13): 190, (9, 12): 200, (9, 13): 210}
elist = [(1, 2),(1,3),(1,8),(2,3),(2,4),(3,6),(4,5),(4,11),(5,6),(5,7),(6,10),(6,14),(7,8),(8,9),(9,10),(9,12),(9,13),(11,12),(11,13),(12,14),(14,13), (2, 1),(3,1),(8,1),(3,2),(4,2),(6,3),(5,4),(11,4),(6,5),(7,5),(10,6),(14,6),(8,7),(9,8),(10,9),(12,9),(13,9),(12,11),(13,11),(14,12),(13,14)]
nodes = 1 + np.arange(14)
# update dist(1,2) if desired
wei[(1,2)] = 1000
# include reversed edges with same distance (so that we can look up (6,5) and (7,8))
wei.update({k[::-1]:v for k,v in wei.items()})
# create lookup function
def wei_func(v, w, data):
return wei[(v,w)]
# build graph without attribute
G = nx.DiGraph()
G.add_nodes_from(nodes)
G.add_edges_from(elist)
list(islice(nx.shortest_simple_paths(G, 1, 2, weight = wei_func),3))