floyd_warshall_numpy#
- floyd_warshall_numpy(G, nodelist=None, weight='weight')[source]#
Find all-pairs shortest path lengths using Floydâ€™s algorithm.
This algorithm for finding shortest paths takes advantage of matrix representations of a graph and works well for dense graphs where all-pairs shortest path lengths are desired. The results are returned as a NumPy array, distance[i, j], where i and j are the indexes of two nodes in nodelist. The entry distance[i, j] is the distance along a shortest path from i to j. If no path exists the distance is Inf.
- Parameters:
- GNetworkX graph
- nodelistlist, optional (default=G.nodes)
The rows and columns are ordered by the nodes in nodelist. If nodelist is None then the ordering is produced by G.nodes. Nodelist should include all nodes in G.
- weight: string, optional (default=â€™weightâ€™)
Edge data key corresponding to the edge weight.
- Returns:
- distance2D numpy.ndarray
A numpy array of shortest path distances between nodes. If there is no path between two nodes the value is Inf.
- Raises:
- NetworkXError
If nodelist is not a list of the nodes in G.
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)\).