Real-world use

Shortest paths and spanning trees are among the most widely deployed graph algorithms. This chapter shows where they run in practice, which libraries to reach for, and the mistakes that most often cause wrong answers.

Where they show up

• Network routing: link-state protocols such as OSPF and IS-IS give every router a map of the network, and each router runs Dijkstra to build its forwarding table. Distance-vector protocols such as RIP are a distributed form of Bellman-Ford.
• Maps and navigation: road networks have millions of vertices, so production routers add preprocessing on top of Dijkstra. A* uses a distance estimate to explore toward the goal, and contraction hierarchies precompute shortcuts so a query touches only a tiny part of the graph.
• Games and robotics: path finding on grids and navigation meshes is usually A* or Dijkstra; 0-1 BFS shows up when some moves are free.
• Network design: an MST is the cheapest way to connect sites with cable, pipes or roads, and it is the starting point for approximating harder problems such as the metric traveling salesman (an MST-based tour is at most twice the optimum).
• Clustering: run Kruskal and stop when k components remain. The result is single-linkage clustering, a common hierarchical method.
• Finance: with weights -log(rate), a negative cycle found by Bellman-Ford corresponds to a currency arbitrage loop.

Libraries

In Python, NetworkX is convenient for prototypes and graphs up to roughly a few hundred thousand edges.

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([("A", "B", 1), ("B", "C", 2), ("A", "C", 3), ("C", "D", 4), ("B", "D", 5)])

print(nx.dijkstra_path(G, "A", "D"))             # ['A', 'B', 'D']
print(nx.dijkstra_path_length(G, "A", "D"))      # 6
mst = nx.minimum_spanning_tree(G, algorithm="kruskal")
print(sorted(mst.edges(data="weight")))          # [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 4)]

For large numeric graphs, SciPy's scipy.sparse.csgraph works on sparse matrices and runs in compiled code.

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra, minimum_spanning_tree

m = csr_matrix(np.array([
    [0, 1, 3, 0],
    [1, 0, 2, 5],
    [3, 2, 0, 4],
    [0, 5, 4, 0],
]))
dist = dijkstra(m, directed=False, indices=0)
print(dist)                              # [0. 1. 3. 6.]
print(minimum_spanning_tree(m).sum())    # 7.0

In C++, the Boost Graph Library provides dijkstra_shortest_paths, bellman_ford_shortest_paths, kruskal_minimum_spanning_tree and prim_minimum_spanning_tree. In databases, Neo4j's Graph Data Science library and PostgreSQL's pgRouting extension run these algorithms close to the data.

Common pitfalls