Real World: Routing Algorithms

Math for CS · Axiom Academy

LESSON Shortest Path Algorithms Dijkstra's and Bellman-Ford: handling positive and negative edge weights Given a weighted directed graph and a source vertex , find the minimum-weight path from to every other vertex. Formally: For each vertex , compute The two classical algorithms differ in what edge weights they support: Dijkstra's: Requires for all edges. Faster. Bellman-Ford: Allows negative edges. Detects negative cycles. Slower. Correctness: Dijkstra's works by a greedy argument. When we extract from the priority queue, . This holds because all edge weights are non-negative, so no future relaxation can improve . Why non-negative weights? If an edge has weight , a vertex we already finalized might later get a shorter path through that negative edge. Dijkstra's greedy extraction would miss it. For sparse graphs ( ), the binary heap gives . For dense graphs ( ), the simple array gives , which beats the heap. Key idea: Relax all edges, times. After iterations, all shortest paths using at most edges are correct. Since any shortest path has at most edges (no cycles in a shortest path), rounds suffice. Negative cycle detection: After rounds, if any edge can still be relaxed, a negative-weight cycle exists. The shortest path is for vertices reachable from this cycle. Bellman-Ford Complexity and Comparison Bellman-Ford time: — passes, each examining all edges. Space: for the distance and parent arrays.

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