dijkstra() takes a graph as a sparse adjacency matrix, where the matrix's stored values represent edge weights/distances, and computes the shortest-path distance from a source node, or every node if indices is omitted, to every other reachable node, returning inf for any node that can't be reached at all. Dijkstra's algorithm specifically requires all edge weights to be non-negative — a negative edge weight can produce incorrect results, since the algorithm's greedy strategy of always expanding the currently-closest node assumes distances can only increase as you explore further, an assumption negative weights violate.
1Understanding csgraph.dijkstra()
dijkstra() takes a graph as a sparse adjacency matrix, where the matrix's stored values represent edge weights/distances, and computes the shortest-path distance from a source node, or every node if indices is omitted, to every other reachable node, returning inf for any node that can't be reached at all. Dijkstra's algorithm specifically requires all edge weights to be non-negative — a negative edge weight can produce incorrect results, since the algorithm's greedy strategy of always expanding the currently-closest node assumes distances can only increase as you explore further, an assumption negative weights violate.
Dijkstra's algorithm requires non-negative edge weights — if your graph might have negative weights, but no negative cycles, use bellman_ford() instead, which correctly handles that case at the cost of being somewhat slower.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
graph = csr_matrix([[0, 1, 5], [0, 0, 2], [0, 0, 0]])
distances = dijkstra(graph, indices=0)
print(distances)2Practical Example
Here is a real-world application of csgraph.dijkstra() showing how it is used in production SciPy code.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
graph = csr_matrix([[0, 1, 5], [0, 0, 2], [0, 0, 0]])
distances, predecessors = dijkstra(graph, indices=0, return_predecessors=True)
print(predecessors)3Best Practices
Follow these guidelines when working with csgraph.dijkstra():
1. Use dijkstra() specifically for graphs with non-negative edge weights, where it's typically faster than more general alternatives
2. Pass indices to compute shortest paths from only specific source nodes, instead of computing the full all-pairs result when you only need a few sources
3. Check for inf values in the result to identify nodes that aren't reachable from a given source, rather than assuming every node is always reachable
Tip: Dijkstra's algorithm requires non-negative edge weights — if your graph might have negative weights, but no negative cycles, use bellman_ford() instead, which correctly handles that case at the cost of being somewhat slower.
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
graph = csr_matrix([[0, 1, 5], [0, 0, 2], [0, 0, 0]])
distances = dijkstra(graph, indices=0)
print(distances)