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()