Shortest Paths

Graph Theory · Axiom Academy

Understanding path optimization in graphs: from BFS to weighted algorithms Given a graph G = (V, E) and vertices s (source) and t (target), find a path from s to t that minimizes some cost measure. There are several variants of this problem: Single-source shortest paths: Find shortest paths from one source vertex to all other vertices Single-pair shortest path: Find the shortest path between two specific vertices All-pairs shortest paths: Find shortest paths between all pairs of vertices 2. Unweighted Graphs: BFS Solution For unweighted graphs (or graphs where all edges have weight 1), Breadth-First Search (BFS) naturally finds shortest paths. A queue of vertices to explore Distance values for each vertex (initially ∞, except source = 0) Parent pointers to reconstruct the path When BFS first reaches a vertex v, it has found the shortest path to v. Why? Because any longer path would have been discovered at a later level. 3. Weighted Graphs: Need for Specialized Algorithms When edges have different weights, BFS no longer guarantees shortest paths. A path with more edges might have lower total weight than a path with fewer edges. Specialized algorithms for weighted graphs include: Dijkstra's Algorithm: Handles non-negative weights, O((V + E) log V) with priority queue Bellman-Ford Algorithm: Handles negative weights, detects negative cycles, O(VE) A* Search: Uses heuristics to guide search toward target, optimal with admissible heuristic

This is the written version of the interactive lesson above. See the full Graph Theory course.