寻找从所有节点到节点的最短路径的有效算法？

Question

我有兴趣找到从所有点到网络中特定点的最短路径。到目前为止，我一直在通过遍历所有点来计算最短路径来估算这一点。

随着网络规模的增加，这种方法的计算成本很高。有有效的替代方案吗？我忽略了 NetworkX 中的任何内容？

# Pseudocode 

For a_node in list_of_nodes:

  shortest_path_to_poi = nx.shortest_path(G, source=a_node, target=poi, method='dijkstra')

感谢您的时间和考虑。

Answer 1

Dijkstra 的算法通常是通过查找从源节点到每个其他节点的所有最短路径来实现的 - 参见例如维基百科。在 NetworkX 中，您可以使用nx.single_source_dijkstra。lengths, paths = nx.single_source_dijkstra(G, source=poi) # paths[v] is the shortest path from poi to the vertex with index v另请参阅nx 文档中的最短路径参考。