Unlike dijkstra(), which computes shortest paths from one or a few specific source nodes, floyd_warshall() computes the complete all-pairs shortest-path matrix in a single call, returning an n-by-n array where entry (i, j) is the shortest distance from node i to node j. It works by iteratively considering every node as a potential waypoint that might shorten the path between every other pair, and unlike Dijkstra's algorithm, it correctly handles negative edge weights, though a negative cycle, a loop whose total weight is negative, still makes the concept of a shortest path undefined, since you could loop around it forever to make the distance arbitrarily small.
1Understanding csgraph.floyd_warshall()
Unlike dijkstra(), which computes shortest paths from one or a few specific source nodes, floyd_warshall() computes the complete all-pairs shortest-path matrix in a single call, returning an n-by-n array where entry (i, j) is the shortest distance from node i to node j. It works by iteratively considering every node as a potential waypoint that might shorten the path between every other pair, and unlike Dijkstra's algorithm, it correctly handles negative edge weights, though a negative cycle, a loop whose total weight is negative, still makes the concept of a shortest path undefined, since you could loop around it forever to make the distance arbitrarily small.
floyd_warshall() computes the full all-pairs shortest-path matrix in one call, which is convenient when you need distances between every pair of nodes, but it's less efficient than dijkstra() when you only actually need paths from one or a few specific source nodes.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
graph = csr_matrix([[0, 1, 0], [0, 0, 2], [0, 0, 0]])
distances = floyd_warshall(graph)
print(distances)2Practical Example
Here is a real-world application of csgraph.floyd_warshall() showing how it is used in production SciPy code.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
graph = csr_matrix([[0, 3, 0], [0, 0, 1], [2, 0, 0]])
distances = floyd_warshall(graph, directed=True)
print(distances[0, 2])3Best Practices
Follow these guidelines when working with csgraph.floyd_warshall():
1. Use floyd_warshall() when you genuinely need all-pairs shortest paths, rather than calling dijkstra() repeatedly for every source node
2. Use dijkstra() or bellman_ford() instead when you only need paths from a small number of specific source nodes, since floyd_warshall()'s all-pairs computation is comparatively wasteful for that case
3. Check for a negative cycle in your graph before relying on the result, since floyd_warshall()'s output is meaningless for pairs connected through a negative cycle
Tip: floyd_warshall() computes the full all-pairs shortest-path matrix in one call, which is convenient when you need distances between every pair of nodes, but it's less efficient than dijkstra() when you only actually need paths from one or a few specific source nodes.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
graph = csr_matrix([[0, 1, 0], [0, 0, 2], [0, 0, 0]])
distances = floyd_warshall(graph)
print(distances)