Case Study • Graph Algorithms

Dijkstra’s Algorithm → Shortest-Path Tree

Designing a step-based learning experience for shortest-path reasoning, edge relaxation, and tree extraction.

Dijkstra’s Algorithm often becomes difficult when learners try to track tentative distances, parent updates, and visited states all at once. This module separates the algorithm into visible decision stages so learners can follow how each update contributes to the final shortest-path tree.

The project uses visualization, guided prediction, and structural comparison to help learners understand not only how the algorithm runs, but also how its final tree differs from a minimum spanning tree.

Watch Demo

Project Scope

Curricular Target

Introductory Data Structures, Algorithms, and graph theory coursework.

Delivery Model

Hybrid instructional module; adaptable for synchronous lecture or asynchronous self-study.

Learner Profile

Computer science beginners learning graph traversal, weighted paths, and algorithmic decision-making.

Primary Objective

Enable students to explain how shortest distances are updated and how parent pointers produce the final shortest-path tree.

Core Learning Outcomes

Explain how relaxation updates tentative distances.
Predict the next selected node based on the smallest tentative value.
Distinguish between a shortest-path tree and a minimum spanning tree.
Construct the shortest-path tree from recorded parent pointers.

Learning Challenge

Learners often understand the idea of “shortest path” in general, but struggle to follow how tentative distances change over time. A second difficulty is conceptual: many students confuse the final shortest-path tree with a minimum spanning tree because both are trees built on weighted graphs.

Design Strategy

Two-Phase Structure

The module first visualizes the algorithmic process, then extracts the final shortest-path tree. This separation helps learners distinguish procedure from result.

State Transparency

Visited nodes, frontier nodes, and newly updated neighbors are visually differentiated so learners can see why each choice is made.

Explicit Relaxation Reasoning

Each update shows how an old tentative value is compared against a new candidate value, reducing the need to hold multiple calculations in working memory.

Misconception Prevention

The final structure is labeled and interpreted as a shortest-path tree, making its purpose distinct from minimum spanning tree logic.

Solution Design

The learning sequence was designed to make shortest-path reasoning visible by externalizing the algorithm’s internal state at each stage.

1. Initialization as a State Setup

The module begins by assigning distance 0 to the start node and infinity to all others. This establishes the initial search state before any traversal occurs.

2. Selection by Smallest Tentative Distance

At each step, the next node is chosen by comparing tentative values. This repeated rule becomes the core decision pattern learners must recognize and predict.

3. Relaxation as Visible Comparison

Edge relaxation is shown as a direct comparison between an existing tentative value and a newly proposed shorter path. This makes update decisions observable rather than hidden.

4. Parent Tracking During Improvement

Every successful update records a parent pointer. This allows learners to understand that the final tree is not created separately, but emerges from the history of improvements.

5. Tree Extraction After Completion

Once the distances are finalized, the visualization builds the shortest-path tree from the parent relationships. This helps learners connect process history to final structure.

Evaluation & Iteration:

Early feedback showed two recurring hesitation points: understanding why one node is selected over another, and understanding how a sequence of parent updates becomes a final tree.

To address this, distance comparisons were made more explicit during relaxation, and the final tree extraction was visually separated from the algorithmic phase to reduce structural confusion.

Instructional Visualization

Part 1 shows Dijkstra’s Algorithm step-by-step. Part 2 extracts the final shortest-path tree from the recorded parent pointers.

Watch actively: pause, predict the next selected node, and decide which edge relaxation changes a distance.

The visualization separates shortest-path computation from final tree construction so learners can follow both the dynamic process and the resulting structure.

Guided Worksheet (Pause & Predict)

These worksheet prompts are aligned to the actual sequence shown in the animation. Pause at each stage, predict the next algorithmic move, then continue to confirm or revise your reasoning.

Part 1 — Initialization

Which vertex is chosen as the start node?
What value should the distance of A be at initialization?
What values should all other vertices receive before any processing begins?
Why is it useful to begin with ∞ for all non-start vertices?

Part 2 — First Selection: Vertex A

Why is A selected first?
Which unprocessed neighbors of A should be considered?
What tentative value should B receive through A?
What tentative value should C receive through A?
Which parent pointers should be recorded after processing A?

Part 3 — Predict the Next Node

After processing A, which vertex should be selected next?
Why is B selected before C?
What rule is used to choose the next vertex?
At this point, what are the tentative values of B and C?

Part 4 — Relaxing from B

Which neighbors of B are still unprocessed?
What new path to C is being tested through B?
Why does C change from 6 to 5?
What tentative value does D receive through B?
Which parent pointer changes after processing B?

Part 5 — Relaxing from C

Why is C selected after B?
Which unprocessed neighbors of C are examined?
What new value does D get when approached through C?
What value does E receive through C?
Why is the update to D considered an improvement over its previous value?

Part 6 — Selection of E

Why is E selected before D?
Which unprocessed neighbors of E are considered?
Does the path from E improve the current value of D? Why or why not?
What tentative value does Z receive through E?
Which parent pointer is set for Z at this stage?

Part 7 — Selection of D

Why is D selected before Z?
Which neighbor of D is still unprocessed?
What new path to Z is tested through D?
Why does Z improve from 16 to 13?
What should the parent of Z become after this update?

Part 8 — Final Selection: Z

Why is Z selected last?
Does Z have any unprocessed neighbors remaining?
What does it mean when Z is finalized with value 13?
At this point, are all reachable vertices complete?

Part 9 — Reading the Final Distance Values

What is the final shortest distance from A to B?
What is the final shortest distance from A to C?
What is the final shortest distance from A to E?
What is the final shortest distance from A to D?
What is the final shortest distance from A to Z?

Part 10 — Building the Shortest-Path Tree

Which parent edge connects B to the tree?
Which parent edge connects C to the tree?
Which parent edge connects E to the tree?
Which parent edge connects D to the tree?
Which parent edge connects Z to the tree?
How do these parent edges differ from simply choosing the globally smallest edges in the graph?

Part 11 — Reflection

Which step was the first time a tentative value improved?
Which update was most important in reaching Z efficiently?
Why is this final tree a shortest-path tree but not a minimum spanning tree?
How did parent pointers help convert the algorithm’s process into a final structure?

Focus on why a value changes, not just which node is visited next. The goal is to understand how shortest paths are built through repeated local updates.

Assessment Strategy

This module evaluates understanding through guided prediction, distance-update reasoning, and interpretation of the final shortest-path tree.

Formative assessment (during learning): Students predict the next selected vertex and justify whether a relaxation should update a value.
- Which unvisited vertex should be selected next, and why?
- What is the current smallest tentative distance available?
- Which neighbor is most likely to receive an updated value in this step?
- Will this relaxation produce an improvement or leave the current value unchanged?
Application assessment (distance + parent reasoning): Students explain how a successful update changes both the distance table and the emerging tree structure.
- What was the old tentative value, and what is the new one?
- Which edge produced the improvement?
- Which parent pointer should be recorded after this update?
- How does this parent relationship contribute to the final shortest-path tree?
Structural interpretation assessment: Students connect the final values and parent pointers to the completed shortest-path tree.
- Which edges appear in the final tree?
- How can you reconstruct the shortest path from A to Z using parent pointers?
- Why does the tree span all reachable vertices from A?
- Which final distance values are shown for B, C, E, D, and Z?
Misconception check (shortest-path tree vs. MST): Students explain why the final result is not a minimum spanning tree.
- Why are parent edges chosen from successful relaxations instead of globally smallest edges?
- What goal does Dijkstra optimize that differs from Kruskal or Prim?
- Can a shortest-path tree and a minimum spanning tree be different on the same graph? Why?
Summative assessment (after learning): A short exit check confirms whether students can independently explain both the process and the final structure.
- Why is the next node always chosen by smallest tentative distance?
- What does edge relaxation do in Dijkstra’s Algorithm?
- How do parent pointers reconstruct shortest paths from the start node?
- How is the final shortest-path tree created from the completed algorithm?

Assessment Activities

Prediction prompts before node-selection steps.
Edge-relaxation checks that compare old and new tentative values.
Parent-pointer tracing from process state to final tree.
Tree interpretation questions that contrast shortest-path trees with minimum spanning trees.

Inclusive Design

Explicit state labels reduce cognitive search during multi-step updates.
Visible distance comparisons support learners who need slower reasoning tempo.
Pacing control supports review at different processing speeds.
Guided worksheet prompts support different learning preferences.

Instructional Impact

The module helps learners move from memorizing the sequence of Dijkstra’s Algorithm to understanding how distance updates, visited states, and parent pointers work together to produce a shortest-path tree.