Routing Basics
22 min
A network is a graph: nodes are routers, edges are links with some
cost (latency, hop count, bandwidth). Finding the best route between
two points is exactly the shortest-path problem from Algorithms'
graph-algorithms module — Dijkstra's algorithm, applied here to
network latency instead of an abstract edge weight.
import heapq
def shortest_path_cost(graph, start, end):
distances = {start: 0}
visited = set()
heap = [(0, start)]
while heap:
dist, node = heapq.heappop(heap)
if node in visited:
continue
visited.add(node)
if node == end:
return dist
for neighbor, weight in graph.get(node, {}).items():
new_dist = dist + weight
if neighbor not in distances or new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return None
This heapq-based priority queue is exactly Data Structures' heaps module in action -- always exploring the currently-cheapest-known path next is what guarantees Dijkstra finds the true shortest path, rather than getting stuck following whichever edge looks shortest one hop at a time.
Write `shortest_path_cost(graph, start, end)`: `graph` maps each node to a dict of `{neighbor: latency}`. Using Dijkstra's algorithm, return the lowest total latency from `start` to `end`, or `None` if `end` is unreachable.
Real internet routers don't run a single global Dijkstra computation for the whole internet. Why not, and what do routing protocols do instead?
You can compute the lowest-latency path through a network graph with Dijkstra's algorithm, and understand why real internet routing uses distributed, local-information protocols instead of one global computation.