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

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)

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)

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)