Real World: Network Routing & Paths

Math for CS · Axiom Academy

How shortest-path algorithms power the internet The internet is a massive graph. Routers are vertices and physical links (fiber optic cables, copper wires, wireless hops) are edges. Each edge has a weight representing cost: latency, bandwidth, or a combination. Routing problem: Given a weighted graph where , find the minimum-weight path from source router to destination router . Every time you load a web page, your data packets traverse a path through this graph. Routing protocols like OSPF and BGP use graph algorithms to compute these paths efficiently. Edsger Dijkstra's 1959 algorithm is the gold standard for single-source shortest paths in graphs with non-negative edge weights. Dijkstra's idea: Maintain a set of vertices whose shortest distances are finalized. Repeatedly extract the unfinalized vertex with the smallest tentative distance, add it to , and relax all edges leaving . Relaxation of edge with weight : d[u] + w(u,v), d[v] d[u] + w(u,v)"> This is essentially a weighted generalization of BFS. Where BFS uses a plain queue (all edges weight 1), Dijkstra uses a priority queue (min-heap) to always process the closest vertex first. Dijkstra's Algorithm Step by Step Consider a network with 5 routers A-E: Init: d[A]=0, all others = . Extract A. Relax A's edges: d[B]=4, d[C]=2. Extract C (smallest). Relax C's edges: d[B]=min(4, 2+1)=3, d[D]=min( , 2+7)=9. Extract B. Relax B's edges: d[D]=min(9, 3+3)=6. Extract D. Relax D's edges: d[E]=min( , 6+1)=7. Extract E.

This is the written version of the interactive lesson above. See the full Math for CS course.