How does Dijkstra's algorithm update distances step-by-step?

Conditions

• Requires a priority queue or list to track unvisited nodes and their current shortest distances.
• The graph must have non-negative edge weights (positive in the pseudocode).

Reasoning, step by step

1. Initialize distances: source = 0, others = infinity.
2. Select the unvisited node with the smallest distance.
3. For each neighbor of the selected node, calculate the tentative distance: dist(current) + weight(edge).
4. If the tentative distance is less than the neighbor's current recorded distance, update the neighbor's distance and predecessor.
5. Mark the selected node as visited.
6. Repeat until all nodes are visited or the target is reached.

Example

In the video example, starting at A (dist 0), it updates B to 4 and C to 2. Then it selects C (dist 2), updating B to 3 (via C, since $2+1 < 4$), D to 6, and E to 7.

Common misconceptions

• Thinking that nodes are visited in alphabetical order or arbitrary order; they are visited in order of increasing shortest distance from the source.
• Assuming that once a distance is set, it never changes; distances are updated (relaxed) whenever a shorter path is found.

Watch the explanation

Explore next

• What is the time complexity of Dijkstra's algorithm with a Fibonacci heap?
• What is the pseudocode for Dijkstra's algorithm?
• Why is Dijkstra's algorithm considered a greedy algorithm?