Unlike dijkstra(), which requires non-negative weights, bellman_ford() correctly computes shortest paths even when some edges have negative weight, by repeatedly relaxing, attempting to improve, every edge's distance estimate across multiple passes rather than greedily finalizing distances early. If the graph contains a negative cycle, a loop whose total edge weight sums to a negative number, bellman_ford() detects this and raises an error, since a shortest path isn't a well-defined, finite concept when you could keep looping around a negative cycle to make a path's total distance arbitrarily small.
1Understanding csgraph.bellman_ford()
Unlike dijkstra(), which requires non-negative weights, bellman_ford() correctly computes shortest paths even when some edges have negative weight, by repeatedly relaxing, attempting to improve, every edge's distance estimate across multiple passes rather than greedily finalizing distances early. If the graph contains a negative cycle, a loop whose total edge weight sums to a negative number, bellman_ford() detects this and raises an error, since a shortest path isn't a well-defined, finite concept when you could keep looping around a negative cycle to make a path's total distance arbitrarily small.
Use bellman_ford() specifically when a graph might have negative edge weights but you still need correct, reliable shortest paths, or when you specifically need to detect whether a negative cycle exists at all — dijkstra() is faster but gives wrong answers on negative weights, without any warning.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
graph = csr_matrix([[0, 1, 0], [0, 0, -1], [0, 0, 0]])
distances = bellman_ford(graph, indices=0)
print(distances)2Practical Example
Here is a real-world application of csgraph.bellman_ford() showing how it is used in production SciPy code.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
graph = csr_matrix([[0, 1, 0], [0, 0, -3], [-1, 0, 0]])
try:
bellman_ford(graph, indices=0)
except Exception as e:
print("Error:", e)3Best Practices
Follow these guidelines when working with csgraph.bellman_ford():
1. Use bellman_ford() instead of dijkstra() specifically when negative edge weights are a realistic possibility in your graph
2. Catch and handle the negative-cycle error explicitly, rather than assuming it will never occur, if your graph's weights come from an untrusted or computed source
3. Prefer dijkstra() when you know all weights are non-negative, since it's typically faster for that common case
Tip: Use bellman_ford() specifically when a graph might have negative edge weights but you still need correct, reliable shortest paths, or when you specifically need to detect whether a negative cycle exists at all — dijkstra() is faster but gives wrong answers on negative weights, without any warning.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
graph = csr_matrix([[0, 1, 0], [0, 0, -1], [0, 0, 0]])
distances = bellman_ford(graph, indices=0)
print(distances)