Dijkstra's Algorithm

Graph Theory · Axiom Academy

Finding the shortest path in weighted graphs using a greedy approach Given a weighted graph and a source vertex, we want to find the shortest distance to every other vertex. The graph below shows vertices connected by edges with positive weights. Key idea: Maintain distance estimates for each vertex and improve them as we explore the graph. Dijkstra's algorithm uses a greedy approach : at each step, select the unvisited vertex with the smallest known distance. This ensures we process vertices in order of their distance from the source. This greedy choice is safe because once we visit a vertex, we've found its shortest path (with non-negative weights). Watch how Dijkstra's algorithm processes each vertex. Starting from vertex A, we: Visit the vertex with minimum distance Update distances to its neighbors Mark the vertex as visited (shown in green) Repeat until all vertices are visited The key operation is relaxation : for each edge (u, v) with weight w, if we can reach v through u with a shorter distance, we update it. This animation shows how distance labels change as we discover better paths through the graph. 5. Why It Works: Correctness Intuition The algorithm's correctness relies on a key observation: when we mark a vertex as visited, we've already found its shortest path.

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