Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

floyd_warshall

floyd_warshall(G, weight='weight')[source]

Find all-pairs shortest path lengths using Floyd’s algorithm.

Parameters:
  • G (NetworkX graph) –
  • weight (string, optional (default= ‘weight’)) – Edge data key corresponding to the edge weight.
Returns:

  • distance (dict) – A dictionary, keyed by source and target, of shortest paths distances between nodes.
  • Notes
  • ——
  • Floyd’s algorithm is appropriate for finding shortest paths
  • in dense graphs or graphs with negative weights when Dijkstra’s algorithm
  • fails. This algorithm can still fail if there are negative cycles.
  • It has running time O(n^3) with running space of O(n^2).

See also

floyd_warshall_predecessor_and_distance(), floyd_warshall_numpy(), all_pairs_shortest_path(), all_pairs_shortest_path_length()