all_pairs_dijkstra_path#
- all_pairs_dijkstra_path(G, cutoff=None, weight='weight')[source]#
Compute shortest paths between all nodes in a weighted graph.
- Parameters:
- GNetworkX graph
- cutoffinteger or float, optional
Length (sum of edge weights) at which the search is stopped. If cutoff is provided, only return paths with summed weight <= cutoff.
- weightstring or function
If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining
u
tov
will beG.edges[u, v][weight]
). If no such edge attribute exists, the weight of the edge is assumed to be one.If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None to indicate a hidden edge.
- Returns:
- pathsiterator
(source, dictionary) iterator with dictionary keyed by target and shortest path as the key value.
See also
floyd_warshall
,all_pairs_bellman_ford_path
Notes
Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.
Examples
>>> G = nx.path_graph(5) >>> path = dict(nx.all_pairs_dijkstra_path(G)) >>> path[0][4] [0, 1, 2, 3, 4]
Additional backends implement this function
- parallelParallel backend for NetworkX algorithms
The parallel implementation first divides the nodes into chunks and then creates a generator to lazily compute shortest paths for each
node_chunk
, and then employs joblib’sParallel
function to execute these computations in parallel across all available CPU cores.- Additional parameters:
- get_chunksstr, function (default = “chunks”)
A function that takes in an iterable of all the nodes as input and returns an iterable
node_chunks
. The default chunking is done by slicing theG.nodes
inton
chunks, wheren
is the number of CPU cores.
[Source]