advanced9 min read·Updated October 2, 2026

Dijkstra's Shortest Path Explained: Tracing Distances in 4 Nodes

Master Dijkstra's shortest path with a complete step-by-step walkthrough of the 0-1-2-3 graph. Build mental models, trace greedy wavefronts, and avoid pitfalls.

By Learnisim AI·Published October 2, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic graph terminology (nodes, directed/undirected edges)
  • Priority queues / min-heaps
  • Greedy algorithm intuition
Dijkstra's Shortest Path: Worked Example (0 → 3) Edges: 0→1:1, 0→2:4, 1→2:1, 1→3:7, 2→3:1 | Optimal Path: 0 → 1 → 2 → 3 (Cost: 3) Graph & Wavefront Exploration 1 4 1 7 1 0 dist: 0 (Start) 1 dist: 1 2 dist: 2 3 dist: 3 (Target) Optimal Path (Cost 3) Suboptimal / Bypassed Wavefront & Relaxation Steps Step 1: Pop (dist: 0, node: 0) Relax neighbors: Node 1 (dist=1), Node 2 (dist=4) PQ State: [(1, 1), (4, 2)] | dist = [0, 1, 4, ∞] Step 2: Pop (dist: 1, node: 1) Relax neighbors: Node 2 (1+1=2 < 4!), Node 3 (1+7=8) PQ State: [(2, 2), (4, 2), (8, 3)] | dist = [0, 1, 2, 8] Step 3: Pop (dist: 2, node: 2) Relax neighbors: Node 3 (2+1=3 < 8!) PQ State: [(3, 3), (4, 2), (8, 3)] | dist = [0, 1, 2, 3] Result: Target Node 3 Reached! Final shortest distance: 3 via path 0 → 1 → 2 → 3 Greedy wavefront guarantees minimum cost without full search.
Dist 0→3 on 0-1:1, 0-2:4, 1-2:1, 1-3:7, 2-3:1 overview diagram
Why

Why Dijkstra's Shortest Path Exists: Routing Through Complexity

Phase 1: The Routing Dilemma

Imagine you are building a navigation system or routing packets across a network, and you need to get from node 0 to node 3. You are given a map with positive edge weights: a path from costs 1, costs 4, costs 1, costs 7, and costs 1. Without a systematic method, how do you know whether to take the seemingly direct route or a longer-looking sequence of smaller hops?
If you just explore blindly or pick the single cheapest local step at every turn, you can easily fall into costly traps. For instance, jumping straight from 0 to 2 costs 4, while routing through node 1 first costs to reach node 2. Greedy local choices or brute-force permutations quickly explode in complexity as networks grow from four nodes to thousands.
We need an algorithm that guarantees we find the absolute minimum cost to reach node 3 (and every other node) without wasting time checking redundant, suboptimal paths.
Dijkstra's Shortest Path: Routing Through Complexity Finding min cost from Node 0 to Node 3 across weighted edges Network Graph Topology 1 4 1 7 1 Node 0 Dist 0 Node 1 Dist 1 Node 2 Dist 2 Node 3 Dist 3 Algorithm Trace & Cost Relaxation 1 Initialize: Dist[0]=0, others = ∞ Queue starts with Node 0 at priority 0 2 Relax Node 0 neighbors: Node 1 (1), Node 2 (4) Update Dist[1] = 1, Dist[2] = 4 3 Visit Node 1 (Dist 1). Relax its neighbors: Node 2: min(4, 1+1) = 2! | Node 3: 1+7 = 8 4 Visit Node 2 (Dist 2). Relax neighbor Node 3: Node 3: min(∞, 2+1) = 3 (via Node 1 & 2) ★ Optimal Path Found: 0 → 1 → 2 → 3 Final Shortest Distance to Node 3 = 3 (beats direct 7)
Why Dijkstra's Shortest Path Exists: Routing Through Complexity diagram
Model

The Greedy Wavefront: Modeling Dijkstra's Search

Phase 2: The Core Mental Model

To understand Dijkstra's shortest path explained, imagine dropping a drop of water into a network of pipes where pipe lengths represent our edge weights. The water flows outward, hitting the nearest junctions first. In graph theory, we mimic this physical wavefront using a priority queue (or min-heap) that always extracts the node with the currently smallest known distance from our start node 0.
In our working example, we have nodes and directed edges with weights: (cost 1), (cost 4), (cost 1), (cost 7), and (cost 1). Our start node is 0. Instead of guessing whether path or path is cheaper, our model maintains two central structures:
1. A distance array (dist), initialized to infinity for all nodes except start (0), representing our upper bound for the shortest distance to each node.
2.A min-heap tracking candidates to explore next, ordered by their tentative distance.
As the algorithm runs, whenever we visit the closest unvisited node, we relax its neighbors—meaning we check if routing through the current node offers a strictly shorter path than previously recorded. If it does, we update our distance array and push the updated cost into our heap.
The Greedy Wavefront: Dijkstra's Shortest Path Algorithm Working Example: Edges (0→1:1, 0→2:4, 1→2:1, 1→3:7, 2→3:1) | Target: Node 3 from Node 0 Graph Topology & Wavefront 1 4 1 7 1 0 Start (dist 0) 1 dist: 1 2 dist: 2 (via 1) 3 Shortest: 3 Optimal Path Result: 0 → 1 → 2 → 3 Total Cost = 1 + 1 + 1 = 3 (beats direct 7) Core Data Structures & Relaxation Steps 1. Distance Array (dist[]) — Upper Bounds Node 0 0 Node 1 1 Node 2 2 Node 3 3 2. Min-Heap (Priority Queue) — Candidates (Node 3, cost 3) - (Node 3, cost 7) Empty / Processed 3. Relaxation & Wavefront Progression 1 Extract Node 0 (dist 0). Relax neighbors 1 & 2. Set dist[1]=1, dist[2]=4. 2 Extract min Node 1 (dist 1). Relax neighbors 2 & 3. • dist[2] updates from 4 → 2 (via 1). • dist[3] updates to 8. 3 Extract min Node 2 (dist 2). Relax neighbor 3. • dist[3] updates from 8 → 3 (via 2). Optimal shortest path found!
The Greedy Wavefront: Modeling Dijkstra's Search diagram
Worked example

Tracing Dijkstra's Algorithm Step by Step on a Four-Node Graph

Phase 3: Worked Example

To see the wavefront model in action, let us trace our locked example: four nodes with directed nonnegative edges (weight 1), (weight 4), (weight 1), (weight 7), and (weight 1). We want to find the shortest path from start node 0 to target node 3.
Given:
- Nodes:
- Edges and weights:
•Start node: 0

- Distance array (initialized to , except dist[0] = 0): dist = [0, inf, inf, inf]
- Priority queue (storing tuples of (distance, node)): pq = [(0, 0)]
Steps:
1. Pop (0, 0) from pq:
•Current node is 0 with distance 0.
•Examine neighbors of 0:

- Node 1: tentative distance = . Since (), update and push (1, 1) to pq.
- Node 2: tentative distance = . Since (), update and push (4, 2) to pq.
- State: dist = [0, 1, 4, inf], pq = [(1, 1), (4, 2)]
2. Pop (1, 1) from pq:
•Current node is 1 with distance 1.
•Examine neighbors of 1:

- Node 2: tentative distance = . Since (4), update and push (2, 2) to pq.
- Node 3: tentative distance = . Since (), update and push (8, 3) to pq.
- State: dist = [0, 1, 2, 8], pq = [(2, 2), (4, 2), (8, 3)] (Note the duplicate entry for node 2 with an older, larger distance).
3. Pop (2, 2) from pq:
•Current node is 2 with distance 2.

- Since this popped distance (2) matches our current , we process its neighbors. (If it were larger than dist[2]—like our upcoming stale (4, 2)—we would skip it). Examine neighbors of 2:
- Node 3: tentative distance = . Since (8), update and push (3, 3) to pq.
- State: dist = [0, 1, 2, 3], pq = [(3, 3), (4, 2), (8, 3)]
4.Pop remaining entries:

- Pop (3, 3): Node 3 is reached with optimal distance 3. It has no outgoing edges in our problem statement.
- Pop (4, 2): Stale entry (4 > dist[2] which is 2), so we skip it.
- Pop (8, 3): Stale entry (8 > dist[3] which is 3), so we skip it.
Result:
- Final distance array: dist = [0, 1, 2, 3]
- The shortest path to node 3 is with a total cost of 3, successfully bypassing the more expensive direct route (cost 8).
Phase 3: Worked Example — Four-Node Shortest Path Trace Finding shortest path from Node 0 to Node 3 via Greedy Wavefront Steps Graph Structure & Final Distances 1 4 1 7 1 N0 dist: 0 N1 dist: 1 N2 dist: 2 N3 dist: 3 (Optimal) Shortest Path: 0 → 1 → 2 → 3 (Cost: 3) Priority Queue & Distance Evolution 1. Pop (0,0) → Relax N1 & N2 dist = [0, 1, 4, ∞] | pq = [(1,1), (4,2)] Node 0 explored; distances updated for neighbors. 2. Pop (1,1) → Relax N2 (better) & N3 dist = [0, 1, 2, 8] | pq = [(2,2), (4,2), (8,3)] Note duplicate entry for Node 2 with older dist (4). 3. Pop (2,2) → Relax N3 (Cost 3) dist = [0, 1, 2, 3] | pq = [(3,3), (4,2), (8,3)] Found optimal route to Node 3 through Node 2. 4. Pop remaining entries & Finish Final dist = [0, 1, 2, 3] Pop (3,3) target reached; stale entries (4,2) & (8,3) skipped. Bypasses direct expensive route 0→1→3 (cost 8).
Tracing Dijkstra's Algorithm Step by Step on a Four-Node Graph diagram
Practice

Predicting Wavefront Evolution on the 0-1-2-3 Network

Phase 4: Practice

Now that you have traced the full execution from node 0 to node 3, let us test your understanding of intermediate wavefront states. Recall our network configuration: edges are (cost 1), (cost 4), (cost 1), (cost 7), and (cost 1). We start at node 0 with best = [0, inf, inf, inf].
Imagine you have just popped node 0, relaxed its neighbors (nodes 1 and 2), and then popped node 1 from your priority queue. At the exact moment node 1 is popped and its outgoing edges are relaxed, what are the contents of the tentative distance array best and the newly pushed entries in the priority queue before any stale elements are popped?
python
# Given network:
# 0->1 (1), 0->2 (4), 1->2 (1), 1->3 (7), 2->3 (1)
# State after popping node 0 and relaxing its neighbors:
best = [0, 1, 4, float('inf')]
pq = [(1, 1), (4, 2)]

# TASK:
# 1. Simulate popping (1, 1) [node 1].
# 2. Relax its neighbors (node 2 via weight 1, node 3 via weight 7).
# Write down the updated `best` array and the new `pq` list contents.
Apply

Transferring Dijkstra's Logic: Navigating Dynamic Edge Mutations

Phase 5: Transfer

We have successfully tracked our wavefront across the locked example , settling final distances via the min-heap to find the optimal cost of 3. But real-world systems are rarely static. What happens when we reuse this exact algorithmic template on perturbed network topographies?
Consider our original graph—edges (1), (4), (1), (7), and (1)—modified in two distinct ways:
1.Unreachable node addition: Node 3 is completely disconnected by removing incoming edges from node 1 and node 2.
2.Zero-weight edge injection: A new direct edge from node 2 to node 3 with weight 0 is introduced.
Recall that our core invariant relies on non-negative edge weights to guarantee that the first time we pop a node from the priority queue, its distance is final. When applying this to our mutated variants, we must verify how the wavefront reacts to infinite bounds and zero-cost transitions.
python
# Conceptual mutation check for Dijkstra's state machine
def check_transfer_variants(dist_array, target):
    if dist_array[target] == float('inf'):
        return "Target is unreachable"
    return f"Optimal cost remains bounded at {dist_array[target]}"
In the first mutation, node 3 retains its initialization value of infinity because no relaxed path can reach it, cleanly signaling unreachability without breaking the algorithm. In the second mutation, the zero-weight edge allows instantaneous cost-free traversal, updating node 3's distance without violating the greedy assumption since .
python
# Given the original locked graph with edges: 0->1(1), 0->2(4), 1->2(1), 1->3(7), 2->3(1)
# Question: Predict how the final distance array [dist[0], dist[1], dist[2], dist[3]] changes 
# if the edge from 1 to 3 is removed AND a new edge from 2 to 3 with weight 0 is added.

FAQ

Why does the path 0-1-2-3 beat 0-1-3 in the worked example?
In the 4-node network, edge 1-3 costs 7, making path 0-1-3 cost 8. However, routing through node 2 via edges 0-1 (1), 1-2 (1), and 2-3 (1) yields a total cost of 3, demonstrating how greedy relaxation finds the true minimum.
Why does Dijkstra's algorithm fail with negative edge weights?
Dijkstra's algorithm relies on the greedy assumption that once a node's shortest distance is finalized, it can never be improved. Negative edges can invalidate this by offering a cheaper path later, requiring algorithms like Bellman-Ford instead.
What is the time complexity of Dijkstra's algorithm using a min-heap?
Using a binary min-heap, the time complexity is O((V + E) log V), where V is the number of vertices and E is the number of edges, because each vertex and edge insertion/extraction involves heap operations.

Keep learning