floyd_warshall_predecessor_and_distance¶
- floyd_warshall_predecessor_and_distance(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: - predecessor,distance (dictionaries) – Dictionaries, keyed by source and target, of predecessors and distances in the shortest path.
- 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(), floyd_warshall_numpy(), all_pairs_shortest_path(), all_pairs_shortest_path_length()