如何加速osmnx(networkx)大图的nx.all_pairs_dijkstra_path_length计算

算法与参数优化 #

• 启用cutoff参数：若业务仅需长度小于某一阈值的路径，给nx.all_pairs_dijkstra_path_length传入cutoff参数，每个节点的Dijkstra搜索到阈值后直接终止，可大幅减少无效计算。
• 替换更适配的算法：osmnx生成的路网无负权边，可改用nx.floyd_warshall_numpy直接生成基于numpy的距离矩阵，向量化计算效率远高于纯Python循环的Dijkstra实现；若边权为整数，也可测试nx.all_pairs_bellman_ford_path_length的性能。
• 预先精简图结构：调用osmnx.simplify_graph方法简化路网，或手动删除孤立节点、不需要计算的末端节点，降低总节点规模，从根源减少计算量。

底层实现替换 #

• 迁移到高性能图计算库：networkx为纯Python实现，性能上限极低。可通过osmnx.utils_graph.graph_to_igraph方法直接将osmnx图转换为igraph（C++底层实现）对象，调用igraph的shortest_paths方法计算全点对距离，速度通常是networkx的10~100倍。也可选择graph-tool库实现同类加速。
• 开启多进程并行：nx.all_pairs_dijkstra_path_length默认单线程执行，可将节点拆分为多个批次，通过concurrent.futures.ProcessPoolExecutor并行计算每个批次节点的单源最短路径，最终合并结果即可，加速比与CPU核心数基本正相关。注意不要使用多线程，Python GIL会导致多线程无法利用多核算力。

业务逻辑优化 #

• 按需计算避免全量计算：若实际仅需部分源点到其他节点的路径，直接对指定源点调用nx.single_source_dijkstra_path_length即可，不需要执行全点对计算。
• 结果缓存复用：若图结构不会频繁变更，首次计算完成后将距离矩阵用numpy.save或pickle序列化存储到本地，后续使用时直接读取，避免重复计算。

内容的提问来源于stack exchange，提问作者Suuuehgi