Dijkstra's algorithm is a fundamental graph algorithm that finds the shortest paths from a single source node to all other nodes in a weighted graph. The algorithm works with graphs that have non-negative edge weights. Let's explore this with a concrete example using a graph with 5 nodes labeled A through E, connected by weighted edges.
Now let's begin the algorithm. In the initialization step, we set the distance to our source node A to zero, since we're already there. All other nodes B, C, D, and E get an initial distance of infinity, representing that we haven't found a path to them yet. We mark all nodes as unvisited and create a priority queue starting with node A and its distance of zero.
Now we begin the main algorithm loop. We visit node A, which has the smallest distance of zero. We mark A as visited, shown in red. Next, we examine A's neighbors: B and C. For node B, the new distance would be A's distance of 0 plus the edge weight of 4, giving us 4. For node C, it's 0 plus 2, giving us 2. We update these distances and add both nodes to our priority queue, with C having priority due to its smaller distance.
Continuing the algorithm, we visit node C with distance 2. We update its neighbors: D gets distance 4, and E gets distance 6. Next, we visit node D with distance 4. When we check D's neighbor E, we find that the path through D gives distance 5, which is better than the previous distance of 6, so we update E's distance. The algorithm completes with final shortest distances: A to A is 0, A to B is 4, A to C is 2, A to D is 4, and A to E is 5. The green path shows the shortest route from A to E.