The Floyd-Warshall algorithm for all pairs shortest paths.
Returns a tuple (distance,path) containing two dictionaries of shortest distance and predecessor paths.
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.
For sparse graphs, see
all_pairs_shortest_path all_pairs_shortest_path_length
which are based on Dijkstra’s algorithm.