有什么方法可以从具有自定义权重的 OSMNX 图计算 NetworkX Dijkstra 的算法吗？

Question

我有以下问题：我想从我之前从 OSMNX 提取的图表中获得最短的 dijkstra_path。默认情况下，NetworkX 的 dijkstra_path 函数使用 OSM 边的长度作为权重来获得最短路径。

就我而言，我不想获得最短距离路径，而是使用我添加到 OSM 边缘的自定义权重获得最短路径。

我把代码分享给你：

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)

然后我们添加两个自定义（随机）权重作为新的边属性，然后我们计算 dijkstra 最短路径并考虑不同的权重。源节点和目标节点充分分离以避免两个节点之间存在唯一的可能路径：

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')

接下来，我们计算三个路由沿返回路径的总累积权重，以检查路由是否不同：

# 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']

最后我们打印三个路由的结果来检查dijkstra的性能：

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

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

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

因此，如您所见，dijkstra 的性能在 weight='length' 和自定义随机权重之间是不同的。但是，考虑到两个不同的自定义权重时返回的路径是完全一样的，这是没有意义的。我已经尝试使用多个源节点和目标节点以及不同类型的自定义权重，并且在所有情况下我都得到了相同的结果。

为了解决这个问题，我想知道是否有人可以向我解释为什么会发生这种情况，以及如何在使用两个不同的自定义权重时获得两条不同的路径和沿途的总成本。 networkX 是从 OSM 边缘获取自定义最短路径的最佳库，还是我应该使用另一个 library/software 来实现？

谢谢！

Answer 1

错误不在 networks 中，而是在您分配自定义长度的创建方式中。您不会将自定义长度添加到 networkx 图 city_graph，而是添加到其他一些变量。因此，在执行具有两个自定义长度的 Dijkstra 算法期间，networks 没有找到任何具有给定标签的边权重，并采用默认值 1，这导致相同的最短路径。

尝试以下最小示例中的内容：

import networkx as nx
import random

random.seed(42)

city_graph = nx.complete_graph(10)

for u,v in city_graph.edges:
    city_graph[u][v]["custom_length"] = random.randint(1, 10)

print(list(city_graph.edges(data=True))[0])
# (0, 1, {'custom_length': 2})

Answer 2

您需要创建一个包含所有"custom weights"的新Graph，然后使用它。新图表 (updated_city_graph) 可以通过以下方式创建：

updated_city_graph = ox.gdfs_to_graph(city_nodes, city_edges)

然后与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')

希望对您有所帮助。

有什么方法可以从具有自定义权重的 OSMNX 图计算 NetworkX Dijkstra 的算法吗？

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

python

dijkstra

openstreetmap

networkx

osmnx