Shortest Path Algorithms

Discrete Math · Axiom Academy

LESSON Shortest Path Algorithms How do we find the shortest path in a weighted graph? Explore Dijkstra's greedy algorithm and understand when Bellman-Ford is necessary. Given a weighted graph and a starting vertex, find the shortest path to all other vertices. Each edge has a weight (cost/distance), and we want to minimize the total weight along our path. Dijkstra's algorithm uses a greedy approach : always process the unvisited vertex with the smallest known distance. It maintains a priority queue of vertices and their tentative distances. Initialize distances: source = 0, all others = ∞ Add all vertices to priority queue While queue not empty: Extract vertex u with minimum distance For each neighbor v of u : If distance[u] + weight(u,v) < distance[v]: Update distance[v] and decrease its priority 3. Why the Greedy Approach Works The key insight: once we process a vertex with the shortest known distance, that distance is optimal and won't change. This works because all edge weights are non-negative. 4. Bellman-Ford: Handling Negative Weights The Bellman-Ford algorithm relaxes all edges repeatedly, allowing it to handle negative edge weights. Instead of greedily choosing the best vertex, it systematically improves all distances. Repeat |V| - 1 times: For each edge (u, v) with weight w: If distance[u] + w < distance[v]: Update distance[v] = distance[u] + w Check for negative cycles (one more iteration)

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