networkx.floyd_warshall

floyd_warshall(G)

The Floyd-Warshall algorithm for all pairs shortest paths.

Parameters:

G : NetworkX graph

Returns:

distance,pred : dictionaries

A dictionary, keyed by source and target, of shortest path distance and predecessors in the shortest path.

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.