Search code examples
pythonnetworkxopenstreetmapdijkstraosmnx

Is there any way to compute NetworkX Dijkstra's algorithm from OSMNX graphs with custom weights?

I have the following problem: I want to get the shortest dijkstra_path from a graph that I have previously extracted from OSMNX. By default, NetworkX's dijkstra_path function uses the length of OSM edges as the weight to get the shortest path.

In my case, I don't want to get the shortest distance path but the shortest path using a custom weight that I have added to OSM edges.

I share with you the code:

import osmnx as ox
import networkx as nx
import numpy as np

city_graph = ox.graph_from_place('Barcelona, Catalunya, Spain', network_type='bike')
city_nodes, city_edges = ox.graph_to_gdfs(city_graph)

Then we add two custom (random) weights as new edges attributes and then we compute dijkstra shortest path taking into account different weights. The source and target nodes are sufficiently separated to avoid having a unique possible path between both nodes:

city_edges['test1'] = np.random.randint(1, 30000, city_edges.shape[0])
city_edges['test2'] = np.random.randint(200, 75000, city_edges.shape[0])

length_path = nx.dijkstra_path(city_graph, source = 30237607, target = 30254084, weight = 'length')
test1_path = nx.dijkstra_path(city_graph, source = 30237607, target = 30254084, weight = 'test1')
test2_path = nx.dijkstra_path(city_graph, source = 30237607, target = 30254084, weight = 'test2')

Next, we calculate the total accumulated weights along the returned path for the three routes just to check if the routes are different:

# LENGTH_PATH

total_length = 0
total_test1 = 0
total_test2 = 0

for i in range(len(length_path)-1):
    total_length = total_length + city_edges.at[city_edges[(city_edges['u']==length_path[i])&(city_edges['v']==length_path[i+1])].index[0], 'length']
    total_test1 = total_test1 + city_edges.at[city_edges[(city_edges['u']==length_path[i])&(city_edges['v']==length_path[i+1])].index[0], 'test1']
    total_test2 = total_test2 + city_edges.at[city_edges[(city_edges['u']==length_path[i])&(city_edges['v']==length_path[i+1])].index[0], 'test2']


# TEST1_PATH

t1_length = 0
t1_test1 = 0
t1_test2 = 0

for i in range(len(test1_path)-1):
    t1_length = t1_length + city_edges.at[city_edges[(city_edges['u']==test1_path[i])&(city_edges['v']==test1_path[i+1])].index[0], 'length']
    t1_test1 = t1_test1 + city_edges.at[city_edges[(city_edges['u']==test1_path[i])&(city_edges['v']==test1_path[i+1])].index[0], 'test1']
    t1_test2 = t1_test2 + city_edges.at[city_edges[(city_edges['u']==test1_path[i])&(city_edges['v']==test1_path[i+1])].index[0], 'test2']


# TEST2_PATH

t2_length = 0
t2_test1 = 0
t2_test2 = 0

for i in range(len(test2_path)-1):
    t2_length = t2_length + city_edges.at[city_edges[(city_edges['u']==test2_path[i])&(city_edges['v']==test2_path[i+1])].index[0], 'length']
    t2_test1 = t2_test1 + city_edges.at[city_edges[(city_edges['u']==test2_path[i])&(city_edges['v']==test2_path[i+1])].index[0], 'test1']
    t2_test2 = t2_test2 + city_edges.at[city_edges[(city_edges['u']==test2_path[i])&(city_edges['v']==test2_path[i+1])].index[0], 'test2']

Finally, we print the results of the three routes to check the performance of dijkstra:

print(total_length)
print(t1_length)
print(t2_length)

enter image description here

print(total_test1)
print(t1_test1)
print(t2_test1)

enter image description here

print(total_test2)
print(t1_test2)
print(t2_test2)

enter image description here

So, as you can see, the performance of dijkstra is different between weight='length' and a custom random weight. However, the path returned when two different custom weights are taken into account is exactly the same, which makes no sense. I've tried with multiple source and target nodes and also with different types of custom weights and the I got the same result in all cases.

To finish with the problem, I want to know if someone can explain me why is this happening and how I can get two different paths and total costs along the route when using two different custom weights. Is networkX the best library to get custom shortest paths from OSM edges or should I use another library/software to do so?

Thanks!

Solution

  • You need to create a new Graph that carries all the "custom weights", then use it. The new Graph (updated_city_graph) can be created with:

    updated_city_graph = ox.gdfs_to_graph(city_nodes, city_edges)

    Then use it with nx.dijkstra_path().

    test1_path = nx.dijkstra_path(updated_city_graph, source = 30237607, target = 30254084, weight = 'test1')
test2_path = nx.dijkstra_path(updated_city_graph, source = 30237607, target = 30254084, weight = 'test2')

    Hope this helps.