Unlock SciPy’s Sparse Graph Algorithms: Shortest Paths, MSTs & More

SciPy provides many common algorithms based on sparse matrix representations, including functions for connected components, Laplacian matrix, shortest‑path calculations, Dijkstra, Floyd‑Warshall, Bellman‑Ford, Johnson, breadth‑first and depth‑first traversals, minimum spanning tree, reverse Cuthill‑McKee ordering, maximum flow, bipartite matching, structural rank, distance‑matrix construction, and utilities for converting between dense and sparse graph formats.

connected_components : connected subgraphs

laplacian : Laplacian matrix of a directed graph

shortest_path : shortest‑path graph

dijkstra : Dijkstra algorithm

floyd_warshall : compute shortest‑path lengths using Floyd‑Warshall

bellman_ford : compute shortest‑path lengths using Bellman‑Ford

johnson : compute shortest‑path lengths using Johnson’s algorithm

breadth_first_order : breadth‑first traversal

depth_first_order : depth‑first traversal

depth_first_tree : depth‑first traversal tree

minimum_spanning_tree : minimum spanning tree of an undirected graph

reverse_cuthill_mckee : permutation array for reverse Cuthill‑McKee ordering of CSR/CSC matrices

maximum_flow : maximum flow

maximum_bipartite_matching : bipartite graph matching

structure_rank : compute structural rank of a graph with a given sparsity pattern

construct_dist_matrix : construct distance matrix

csgraph_from_dense : build CSR sparse graph from dense matrix

csgraph_from_masked : build CSR graph from masked array

csgraph_masked_from_dense : construct masked graph from dense matrix

csgraph_to_dense : convert sparse graph to dense matrix

csgraph_to_masked : convert sparse graph to masked representation

<code>from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = [
    [0, 1, 2, 0],
    [0, 0, 0, 1],
    [2, 0, 0, 3],
    [0, 0, 0, 0]
]
graph = csr_matrix(graph)
print(graph)

dist_matrix, predecessors = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)
print(dist_matrix)
print(predecessors)
</code>

<code>from scipy.sparse.csgraph import shortest_path

graph = [
    [0, 1, 2, 0],
    [0, 0, 0, 1],
    [2, 0, 0, 3],
    [0, 0, 0, 0]
]
graph = csr_matrix(graph)

dist_matrix, predecessors = shortest_path(csgraph=graph, directed=False, indices=0, return_predecessors=True)
print(dist_matrix)
print(predecessors)
</code>

<code>from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = [
    [0, 1, 2, 0],
    [0, 0, 0, 1],
    [2, 0, 0, 3],
    [0, 0, 0, 0]
]
graph = csr_matrix(graph)
print(graph)

dist_matrix, predecessors = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)
print(dist_matrix)
print(predecessors)
</code>