优化 osmnx 网络中的最短路径计算

Question

我的问题很简单。我必须计算 osmnx 网络中所有节点之间的最短路径。然而，这需要大量时间。我想知道是否有什么可以加快 up/optimize 这个过程。提前谢谢你。

代码如下：

import osmnx as ox
import igraph as ig
import matplotlib.pyplot as plt
import pandas as pd
import networkx as nx
import numpy as np
import matplotlib as mpl
import random as rd
from IPython.display import clear_output
ox.config(log_console=True, use_cache=True)


%%time
city = 'Portugal, Lisbon'
G = ox.graph_from_place(city, network_type='drive')

G_nx = nx.relabel.convert_node_labels_to_integers(G)

weight = 'length'

G_ig = ig.Graph(directed=True)
G_ig.add_vertices(list(G_nx.nodes()))
G_ig.add_edges(list(G_nx.edges()))
G_ig.vs['osmid'] = list(nx.get_node_attributes(G_nx, 'osmid').values())
G_ig.es[weight] = list(nx.get_edge_attributes(G_nx, weight).values())

assert len(G_nx.nodes()) == G_ig.vcount()
assert len(G_nx.edges()) == G_ig.ecount()
nodes, edges = ox.graph_to_gdfs(G, nodes=True, edges=True) 

%%time
L_back_total = []
L_going_total =[]
i=1

for element in G_nx.nodes:

    clear_output(wait=True)
    L_going=[]
    L_back=[]
    
    for node in G_nx.nodes:
        
        length_going = G_ig.shortest_paths(source=element, target=node, weights=weight)[0][0]
        length_back = G_ig.shortest_paths(source=node, target=element, weights=weight)[0][0]
        
        L_going.append(length_going)
        L_back.append(length_back)

    L_back_total.append(length_back)
    L_going_total.append(length_going)
    print('Progress:', np.round(i/len(G_nx.nodes)*100, 5))
    i+=1

Answer 1

考虑使用 Floyd-Warshall 算法。

文档： https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html

用法：

nx.floyd_warshall(G_ig)

Answer 2

在 osmnx 提供的示例中，有一个关于 routing-speed-time 的笔记本显示了如何并行化计算

优化 osmnx 网络中的最短路径计算

Optimize shortest path calculation in an osmnx network

python

optimization

networkx

igraph

osmnx