Is all_pairs_dijkstra faster than multiple dijkstra_path?

Question

Is all_pairs_dijkstra just a dijkstra_path with a for loop, or are all shortest path routes calculated all at once in the all_pairs_dijkstra?

Is it faster to do one all_pairs_dijkstra or many dijkstra_path in a for loop?

Answer 1

Although I can't specifically speak to how networkx implements this function, using Dijkstra's algorithm to solve the all pairs shortest paths problem just means running one copy of Dijkstra's algorithm starting from each node in the graph to compute the pairwise distances.

In deciding whether to use a for loop around a single call or to use the all_pairs_dijkstra function, I'd recommend using all_pairs_dijkstra unless you have a compelling reason not to do so, as that function explicitly telegraphs your intent. Plus, if there are any optimizations done behind the scenes, you would be able to take advantage of them.

But specifically for networkx, is there any reason not to just use the simpler all_shortest_paths function? I imagine this is even simpler and would be a good call unless you have a specific reason to use all_pairs_dijkstra.

Answer 2

Networkx implementation of all_pairs_dijkstra and alike uses memoization in form of a heap to memorize what node had already been visited. That makes it way faster compared to iterating over the cross product and using nx.shortest_path manually.

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)