ToolSphere
Back to all articles
student

Dijkstra's Algorithm Example: Step by Step

2026-11-109 min read

Try it: free Graph Algorithm Visualizer

Trace graph searches, shortest paths and spanning trees

Open →

Dijkstra's algorithm is the foundational single-source shortest path algorithm for directed or undirected graphs with nonnegative edge weights. Introduced by Edsger W. Dijkstra in 1956 and published in 1959, it solves a fundamental problem: given a weighted graph and a starting vertex, what is the minimum total weight needed to reach every other vertex?

Undergraduate computer science courses (such as UC Berkeley CS 61B/170, MIT 6.1210, and Stanford CS 161) frequently test this algorithm on exams. Exam questions expect students to maintain a min-priority queue and a distance table across every extraction step, compute edge relaxations accurately, and reconstruct the resulting shortest path tree.

This guide traces Dijkstra's algorithm on the canonical textbook graph (from Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms, Chapter 24). Every distance, queue state, and predecessor update below is verified directly against ToolSphere's graph algorithm library. We also examine why Dijkstra fails when negative edges are introduced, why adding a constant to all edges does not repair it, and how the Bellman-Ford algorithm resolves negative edge weights.


The Graph and Initial Conditions

Consider a directed, weighted graph with 5 vertices: s, t, x, y, and z. The source vertex is s.

The graph contains 10 directed edges with the following integer weights:

Edge (from → to) : Weight
s → t : 10
s → y : 5
t → x : 1
t → y : 2
x → z : 4
y → t : 3
y → x : 9
y → z : 2
z → s : 7
z → x : 6

In adjacency list representation:

  • s: [(t, 10), (y, 5)]
  • t: [(x, 1), (y, 2)]
  • x: [(z, 4)]
  • y: [(t, 3), (x, 9), (z, 2)]
  • z: [(s, 7), (x, 6)]

Notice that multiple routes exist between vertices. For instance, t can be reached directly from s with weight 10, or indirectly via y (s → y → t) with total weight 5 + 3 = 8. Dijkstra's greedy strategy systematically discovers which path is truly minimal.


Core Algorithm Mechanics

Dijkstra's algorithm maintains three primary data structures:

  1. Distance array (d): Stores the current shortest known distance from the source s to each vertex. Unvisited vertices start at infinity (∞), and d[s] = 0.
  2. Predecessor array (p): Tracks the parent vertex that immediately precedes each node on the shortest known path, initialized to null.
  3. Min-priority queue (Q): Holds all unsettled vertices, prioritized by their current distance estimate d[v].

The Edge Relaxation Rule

When an edge (u, v) with weight w(u, v) is evaluated, the algorithm checks whether routing through u offers a shorter path to v than previously recorded:

if d[u] + w(u, v) < d[v]:
    d[v] = d[u] + w(u, v)
    p[v] = u
    decrease_key(Q, v, d[v])

If the candidate distance is strictly less than d[v], d[v] is updated, p[v] records u as v's predecessor, and v's position in the priority queue is updated (a decrease-key operation).


Step-by-Step Execution Trace

Below is the complete trace of Dijkstra's algorithm running on the 5-vertex graph, starting at s.

Step 0: Initialization

Set the source distance d[s] = 0 and all other distances to ∞. All predecessors are null. Insert all 5 vertices into the priority queue Q.

  • Priority Queue (Q): [s: 0, t: ∞, x: ∞, y: ∞, z: ∞]
  • Distances: s = 0, t = ∞, x = ∞, y = ∞, z = ∞
  • Predecessors: s = null, t = null, x = null, y = null, z = null

Step 1: Extract Vertex s

Extract the minimum element from Q: s with d[s] = 0. Node s is now settled (its shortest distance is finalized).

Inspect outgoing edges from s:

  1. Edge s → t (weight 10):
    • Candidate distance: d[s] + 10 = 0 + 10 = 10.
    • Comparison: 10 < d[t] (∞).
    • Update: d[t] = 10, p[t] = s.
  2. Edge s → y (weight 5):
    • Candidate distance: d[s] + 5 = 0 + 5 = 5.
    • Comparison: 5 < d[y] (∞).
    • Update: d[y] = 5, p[y] = s.
  • Priority Queue (Q): [y: 5, t: 10, x: ∞, z: ∞]
  • Distances: s = 0, t = 10, x = ∞, y = 5, z = ∞
  • Predecessors: s = null, t = s, x = null, y = s, z = null

Step 2: Extract Vertex y

Extract the minimum element from Q: y with d[y] = 5. Node y is settled.

Inspect outgoing edges from y:

  1. Edge y → t (weight 3):
    • Candidate distance: d[y] + 3 = 5 + 3 = 8.
    • Comparison: 8 < d[t] (10).
    • Update: d[t] = 8, p[t] = y. Notice that this relaxes the earlier direct path from s!
  2. Edge y → x (weight 9):
    • Candidate distance: d[y] + 9 = 5 + 9 = 14.
    • Comparison: 14 < d[x] (∞).
    • Update: d[x] = 14, p[x] = y.
  3. Edge y → z (weight 2):
    • Candidate distance: d[y] + 2 = 5 + 2 = 7.
    • Comparison: 7 < d[z] (∞).
    • Update: d[z] = 7, p[z] = y.
  • Priority Queue (Q): [z: 7, t: 8, x: 14]
  • Distances: s = 0, t = 8, x = 14, y = 5, z = 7
  • Predecessors: s = null, t = y, x = y, y = s, z = y

Step 3: Extract Vertex z

Extract the minimum element from Q: z with d[z] = 7. Node z is settled.

Inspect outgoing edges from z:

  1. Edge z → s (weight 7):
    • Candidate distance: d[z] + 7 = 7 + 7 = 14.
    • Vertex s is already settled and not in Q. In standard Dijkstra, finalized vertices are not updated. Even if checked, 14 > d[s] (0), so no relaxation occurs.
  2. Edge z → x (weight 6):
    • Candidate distance: d[z] + 6 = 7 + 6 = 13.
    • Comparison: 13 < d[x] (14).
    • Update: d[x] = 13, p[x] = z.
  • Priority Queue (Q): [t: 8, x: 13]
  • Distances: s = 0, t = 8, x = 13, y = 5, z = 7
  • Predecessors: s = null, t = y, x = z, y = s, z = y

Step 4: Extract Vertex t

Extract the minimum element from Q: t with d[t] = 8. Node t is settled.

Inspect outgoing edges from t:

  1. Edge t → y (weight 2):
    • Vertex y is already settled (y ∉ Q). No update.
  2. Edge t → x (weight 1):
    • Candidate distance: d[t] + 1 = 8 + 1 = 9.
    • Comparison: 9 < d[x] (13).
    • Update: d[x] = 9, p[x] = t. This third update to x reveals the optimal route!
  • Priority Queue (Q): [x: 9]
  • Distances: s = 0, t = 8, x = 9, y = 5, z = 7
  • Predecessors: s = null, t = y, x = t, y = s, z = y

Step 5: Extract Vertex x

Extract the minimum element from Q: x with d[x] = 9. Node x is settled.

Inspect outgoing edges from x:

  1. Edge x → z (weight 4):
    • Vertex z is already settled (z ∉ Q). No update.
  • Priority Queue (Q): [] (empty)
  • Distances: s = 0, t = 8, x = 9, y = 5, z = 7
  • Predecessors: s = null, t = y, x = t, y = s, z = y

With Q empty, the algorithm terminates. Every vertex reachable from s has received its final, provably minimal distance.


State Table: Distance and Predecessor Evolution

The table below summarizes the exact state of the algorithm after initialization and after each extraction iteration. Each entry displays d[v] (p[v]).

Iteration Extracted Vertex Settled Nodes Priority Queue Remaining d[s] d[t] d[x] d[y] d[z]
Init — ∅ [s:0, t:∞, x:∞, y:∞, z:∞] 0 (—) ∞ (—) ∞ (—) ∞ (—) ∞ (—)
Pass 1 s (cost 0) {s} [y:5, t:10, x:∞, z:∞] 0 (—) 10 (s) ∞ (—) 5 (s) ∞ (—)
Pass 2 y (cost 5) {s, y} [z:7, t:8, x:14] 0 (—) 8 (y) 14 (y) 5 (s) 7 (y)
Pass 3 z (cost 7) {s, y, z} [t:8, x:13] 0 (—) 8 (y) 13 (z) 5 (s) 7 (y)
Pass 4 t (cost 8) {s, y, z, t} [x:9] 0 (—) 8 (y) 9 (t) 5 (s) 7 (y)
Pass 5 x (cost 9) {s, y, z, t, x} [] 0 (—) 8 (y) 9 (t) 5 (s) 7 (y)

Shortest Path Reconstruction

To construct the shortest path from s to any destination vertex, trace the predecessor links backward until reaching s:

  • Path to s: s (Distance: 0)
  • Path to y: p[y] = s → Path: s → y (Distance: 5)
  • Path to z: p[z] = y, p[y] = s → Path: s → y → z (Distance: 5 + 2 = 7)
  • Path to t: p[t] = y, p[y] = s → Path: s → y → t (Distance: 5 + 3 = 8)
  • Path to x: p[x] = t, p[t] = y, p[y] = s → Path: s → y → t → x (Distance: 5 + 3 + 1 = 9)

The shortest path tree consists of directed edges {(s, y), (y, z), (y, t), (t, x)}. Note that direct edge (s, t) of weight 10 is excluded because detour s → y → t costs only 8. Similarly, direct edge (y, x) of weight 9 is excluded because path y → t → x costs only 3 + 1 = 4.


Why Dijkstra Fails on Negative Edge Weights

Dijkstra's correctness depends on a greedy invariant: once a vertex u is extracted from the priority queue, its distance d[u] is final.

Because all edge weights w ≥ 0, any alternate unvisited path from s to u through some other unsettled vertex v must have cost:

Cost(s → ... → v → ... → u) ≥ d[v] ≥ d[u]

Since d[v] ≥ d[u], further extension along positive edges can never produce a sum smaller than d[u].

The Counterexample

When edges can have negative weights, this mathematical property collapses completely. Consider a 3-vertex directed graph:

  • Vertices: A, B, C
  • Edges:
    • A → B (weight 1)
    • A → C (weight 3)
    • C → B (weight −5)
  • Source: A

Let us trace how naive Dijkstra behaves on this graph:

  1. Initialize: d[A] = 0, d[B] = ∞, d[C] = ∞. Priority Queue: [A: 0, B: ∞, C: ∞].
  2. Extract A (0):
    • Relax A → B: d[B] = 0 + 1 = 1, p[B] = A.
    • Relax A → C: d[C] = 0 + 3 = 3, p[C] = A.
    • Priority Queue: [B: 1, C: 3].
  3. Extract B (1):
    • Node B has the minimum distance in Q (1 < 3).
    • Dijkstra greedily extracts B and declares d[B] = 1 permanently settled!
  4. Extract C (3):
    • Node C has outgoing edge C → B with weight −5.
    • The path A → C → B has total weight 3 + (−5) = −2.
    • However, standard Dijkstra considers B already finalized and does not re-enter it into the priority queue.

Outcome: Dijkstra outputs d[B] = 1, but the true shortest path is A → C → B with distance −2. Dijkstra's greedy choice produces an incorrect result.

       1
   A ────→ B  (Dijkstra finalizes B at distance 1)
    \     ↑
   3 \   / −5
      v /
       C      (Path A → C → B has true distance −2)

Why Adding a Constant Fails

A common student intuition is: "Why not find the minimum negative edge weight −k, add k to every edge in the graph so all weights become non-negative, run Dijkstra, and subtract the offset?"

This transformation fails because adding a constant penalizes paths with more edges.

Suppose:

  • Path 1 has 1 edge of weight 4.
  • Path 2 has 3 edges of weights 2, −5, and 1 (total weight: 2 − 5 + 1 = −2).

Path 2 is shorter (−2 < 4). If we add +6 to every edge to remove negative values:

  • New Path 1: 4 + 6 = 10 (1 edge).
  • New Path 2: (2+6) + (−5+6) + (1+6) = 8 + 1 + 7 = 16 (3 edges).

Now Path 1 has total weight 10 while Path 2 has total weight 16! Adding a constant disproportionately inflates paths containing more edges, altering the true shortest path.


How Bellman-Ford Handles Negative Edges

The Bellman-Ford algorithm uses dynamic programming rather than greedy extraction, eliminating the requirement for nonnegative edge weights.

Instead of declaring vertices finalized one by one, Bellman-Ford performs |V| − 1 complete passes over every edge in the graph. In each pass, every edge (u, v) is relaxed:

for pass from 1 to |V| - 1:
    for each edge (u, v) with weight w:
        if d[u] != ∞ and d[u] + w < d[v]:
            d[v] = d[u] + w
            p[v] = u

Why |V| − 1 Passes Are Sufficient

In any graph without negative-weight cycles, the shortest path between any two vertices is a simple path (a path without repeating vertices). A simple path visiting at most |V| vertices contains at most |V| − 1 edges.

  • Pass 1 computes the shortest distances for all paths using at most 1 edge.
  • Pass 2 computes the shortest distances for all paths using at most 2 edges.
  • Pass k computes the shortest distances for all paths using at most k edges.

After |V| − 1 passes, all simple shortest paths are guaranteed to be resolved, regardless of whether edge weights are positive or negative.

Verifying the Counterexample with Bellman-Ford

Running Bellman-Ford on the 3-vertex counterexample (A → B: 1, A → C: 3, C → B: −5):

  • Init: d[A] = 0, d[B] = ∞, d[C] = ∞
  • Pass 1:
    • Relax A → B: d[B] = 1, p[B] = A
    • Relax A → C: d[C] = 3, p[C] = A
    • Relax C → B: d[B] = 3 + (−5) = −2, p[B] = C
  • Pass 2: All edges checked; no values change.

Bellman-Ford correctly concludes d[B] = −2 with path A → C → B.

Detecting Negative Cycles

A negative-weight cycle is a cycle whose edge weights sum to less than zero. If such a cycle is reachable from the source, one can traverse the cycle infinitely many times, driving the distance to −∞.

Bellman-Ford detects reachable negative cycles by performing a |V|-th pass:

for each edge (u, v) with weight w:
    if d[u] != ∞ and d[u] + w < d[v]:
        report "Reachable negative cycle detected!"

If any edge can still be relaxed after |V| − 1 passes, a negative cycle exists. ToolSphere's graph engine flags all nodes reachable from the cycle with distance −∞.


Algorithm Comparison: Dijkstra vs. Bellman-Ford

Feature Dijkstra's Algorithm Bellman-Ford Algorithm
Problem Type Single-Source Shortest Path Single-Source Shortest Path
Strategy Greedy (Min-Priority Queue) Dynamic Programming (Edge Relaxation)
Edge Weights Nonnegative weights only (w ≥ 0) Any weights (positive, zero, or negative)
Negative Cycles Cannot detect; produces incorrect outputs Detects reachable negative cycles (−∞)
Time Complexity O((V + E) log V) with binary heap O(V · E)
Best Used For Large sparse road networks, network routing (OSPF) Arbitrage detection, distance-vector routing (RIP)

For dense graphs where E ≈ V², Dijkstra using an adjacency matrix and simple array search runs in O(V²). Using a Fibonacci heap achieves O(V log V + E), although constant factors favor binary heaps in practical implementations.


Frequently Asked Questions

1. Can Dijkstra work on undirected graphs?

Yes. An undirected graph with nonnegative edge weights is equivalent to a directed graph where each undirected edge between u and v is replaced by two directed edges: (u, v) and (v, u) with identical weights. Dijkstra runs identically on this symmetric structure.

2. What happens if multiple shortest paths have the same distance?

When multiple paths share the minimal total weight, Dijkstra will return one valid shortest path tree. The exact path selected depends on how the priority queue breaks ties between equal keys. Tie-breaking rules do not change the final distance values, which remain unique.

3. What is the difference between Dijkstra and Prim's algorithm?

Both algorithms extract vertices greedily from a min-priority queue and maintain an unsettled set. However, their relaxation keys answer fundamentally different questions:

  • Dijkstra: The key of vertex v is the cumulative path distance from the source: d[u] + w(u, v).
  • Prim: The key of vertex v is the weight of the single cheapest edge connecting v to the growing minimum spanning tree: w(u, v).

4. What if the target vertex is unreachable from the source?

Unreachable vertices remain with distance ∞ and predecessor null. In standard Dijkstra, once all remaining vertices in the priority queue have distance ∞, the algorithm can terminate early because no further finite paths exist.

5. Why doesn't Dijkstra revisit settled nodes?

By design, Dijkstra guarantees that when a node u is extracted from the min-priority queue, no future path can be shorter (assuming w ≥ 0). Not revisiting settled nodes maintains the optimal O((V + E) log V) runtime. Allowing settled nodes to be re-inserted turns the algorithm into a variant of Bellman-Ford (like SPFA), which can degrade to exponential time in pathological cases.

6. Can Dijkstra be used to find the longest path?

No. Finding the longest simple path in a general graph is NP-hard. In a Directed Acyclic Graph (DAG), longest paths can be found in O(V + E) time by topological sorting or by negating edge weights and running a DAG shortest path algorithm.

7. How does A* search compare to Dijkstra?

A* search is an extension of Dijkstra's algorithm that incorporates a heuristic estimate h(v) of the remaining distance to a goal. At each step, A* prioritizes vertices by f(v) = g(v) + h(v), where g(v) is the exact distance from the source and h(v) is an admissible heuristic. When h(v) = 0 for all nodes, A* reduces exactly to Dijkstra.

8. Does Dijkstra find all-pairs shortest paths?

No. Dijkstra solves single-source shortest paths from one specific source vertex. To compute all-pairs shortest paths:

  • On graphs with nonnegative weights: Run Dijkstra |V| times, taking O(V · E log V) time.
  • On graphs with negative weights but no negative cycles: Use Johnson's algorithm (O(V · E + V² log V)) or the Floyd-Warshall algorithm (O(V³)).

Try It in the Graph Visualizer

Experiment with Dijkstra's algorithm, inspect priority queues, and compare step-by-step traces against BFS, DFS, Bellman-Ford, Prim, Kruskal, and topological sort on ToolSphere's interactive Graph Algorithm Visualizer. You can edit vertices, modify weights, test tie-breaking rules, and trace each edge relaxation directly in your browser.

Use the Data Structure Visualizer to trace tree and heap operations. For a related walkthrough, read Binary Heap: Insert and Delete Step by Step.

Looking for other tools?

Explore ToolSphere Homepage →