networkx.floyd_warshall

floyd_warshall(G, huge=inf)

The Floyd-Warshall algorithm for all pairs shortest paths.

Returns a tuple (distance,path) containing two dictionaries of shortest distance and predecessor paths.

Parameters:G : NetworkX graph

See also

all_pairs_shortest_path, all_pairs_shortest_path_length

Notes

This algorithm is most appropriate for dense graphs. The running time is O(n^3), and running space is O(n^2) where n is the number of nodes in G.