all_pairs_dijkstra 比多个 dijkstra_path 快吗？

Question

all_pairs_dijkstra只是一个带有for循环的dijkstra_path，还是all_pairs_dijkstra中一次性计算出所有最短路径路由？

在 for 循环中执行一个 all_pairs_dijkstra 还是执行多个 dijkstra_path 更快？

Answer 1

虽然我不能具体说networkx是如何实现这个功能的，但是使用Dijkstra算法解决所有对最短路径问题只是意味着运行Dijkstra算法的一个副本，从图中的每个节点开始到计算成对距离。

在决定是围绕单个调用使用 for 循环还是使用 all_pairs_dijkstra 函数时，我建议使用 all_pairs_dijkstra 除非你有令人信服的理由不这样做这样做，因为该功能明确传达了您的意图。另外，如果在幕后进行了任何优化，您将能够利用它们。

但特别是对于 networkx，有什么理由不只使用更简单的 all_shortest_paths 函数吗？我想这会更简单，除非您有特定理由使用 all_pairs_dijkstra.

，否则这是一个很好的选择

Answer 2

all_pairs_dijkstra 等的 Networkx 实现使用记忆 in form of a heap 来记住已经访问过的节点。与迭代叉积和手动使用 nx.shortest_path 相比，这使得它更快。

import networkx as nx
from itertools import product

G = nx.grid_2d_graph(20,20)

%timeit -n 3 -r 2 sum([nx.shortest_path_length(G, u, v) for u, v in product(G.nodes, G.nodes)])
17.2 s ± 158 ms per loop (mean ± std. dev. of 2 runs, 3 loops each)

%timeit -n 3 -r 2 sum([ d for t in nx.all_pairs_dijkstra_path_length(G) for d in t[1].values() ])
335 ms ± 1.29 ms per loop (mean ± std. dev. of 2 runs, 3 loops each)

all_pairs_dijkstra 比多个 dijkstra_path 快吗？

Is all_pairs_dijkstra faster than multiple dijkstra_path?

python

networkx

graph-theory

shortest-path

dijkstra