Shortest paths & minimum spanning trees guide · 6/6

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

Using Dijkstra with negative edges. It does not raise an error; it silently returns wrong distances. Validate the input or use Bellman-Ford.
Forgetting the stale-entry check if d > dist[u]. Results stay correct, but the run can slow down sharply on dense graphs.
Adding only one direction of an undirected edge.
Overflow: in C++ or Java, INF + w wraps around. Never relax from a vertex whose distance is still infinite, and use 64-bit integers.
Floating-point weights: sums of decimals are inexact, so compare with care or scale to integers (cents, milliseconds).
Heap ties: Python compares tuples element by element. If two entries share a distance and the second item is not comparable, heappush raises TypeError. Add a counter as a tie-breaker.

import heapq
from itertools import count

tie = count()
heap = []
heapq.heappush(heap, (5, next(tie), {"name": "warehouse"}))
heapq.heappush(heap, (5, next(tie), {"name": "store"}))   # no TypeError: the counter decides
print(heapq.heappop(heap)[2])                              # {'name': 'warehouse'}

MST on a disconnected graph: Kruskal returns a forest with fewer than V - 1 edges. Check the count before treating it as a tree.

Summary

Dijkstra powers link-state routing and, with preprocessing, map navigation; Bellman-Ford underlies distance-vector routing.
MSTs serve network design, clustering and approximation algorithms.
Use NetworkX for convenience and SciPy or Boost for scale.
Most bugs come from negative weights, missing reverse edges, overflow and heap tie-breaking.

0 comments

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

Common pitfalls

Using Dijkstra with negative edges. It does not raise an error; it silently returns wrong distances. Validate the input or use Bellman-Ford.

Forgetting the stale-entry check if d > dist[u]. Results stay correct, but the run can slow down sharply on dense graphs.

Adding only one direction of an undirected edge.

Overflow: in C++ or Java, INF + w wraps around. Never relax from a vertex whose distance is still infinite, and use 64-bit integers.

Floating-point weights: sums of decimals are inexact, so compare with care or scale to integers (cents, milliseconds).

Heap ties: Python compares tuples element by element. If two entries share a distance and the second item is not comparable, heappush raises TypeError. Add a counter as a tie-breaker.

import heapq from itertools import count tie = count() heap = [] heapq.heappush(heap, (5, next(tie), {"name": "warehouse"})) heapq.heappush(heap, (5, next(tie), {"name": "store"})) # no TypeError: the counter decides print(heapq.heappop(heap)[2]) # {'name': 'warehouse'}

MST on a disconnected graph: Kruskal returns a forest with fewer than V - 1 edges. Check the count before treating it as a tree.

Summary

Dijkstra powers link-state routing and, with preprocessing, map navigation; Bellman-Ford underlies distance-vector routing.

MSTs serve network design, clustering and approximation algorithms.

Use NetworkX for convenience and SciPy or Boost for scale.

Most bugs come from negative weights, missing reverse edges, overflow and heap tie-breaking.

Real-world use

Where they show up

Libraries

Common pitfalls

Summary

Further reading

0 comments

Real-world use

Where they show up

Libraries

Common pitfalls

Summary

Further reading

0 comments