retworkx.floyd_warshall¶
- floyd_warshall(dag, /)¶
Return the shortest path lengths between ever pair of nodes that has a path connecting them
The runtime is \(O(|N|^3 + |E|)\) where \(|N|\) is the number of nodes and \(|E|\) is the number of edges.
This is done with the Floyd Warshall algorithm:
Process all edges by setting the distance from the parent to the child equal to the edge weight.
Iterate through every pair of nodes (source, target) and an additional itermediary node (w). If the distance from source \(\rightarrow\) w \(\rightarrow\) target is less than the distance from source \(\rightarrow\) target, update the source \(\rightarrow\) target distance (to pass through w).
The return format is
{Source Node: {Target Node: Distance}}
.Note
Paths that do not exist are simply not found in the return dictionary, rather than setting the distance to infinity, or -1.
Note
Edge weights are restricted to 1 in the current implementation.
- Parameters
graph (PyDigraph) – The DiGraph to get all shortest paths from
- Returns
A dictionary of shortest paths
- Return type
dict