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实现使用memoization 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)