Shortest Path and Minimum Spanning Tree Algorithms

Active learning works for shortest path and minimum spanning tree algorithms because these topics demand repeated practice tracing steps and comparing outcomes. Students benefit from hands-on graph manipulation where they see how greedy choices and edge relaxations play out in real time, building both intuition and algorithmic reasoning.

• JC 2
• Computing
• 4 activities
• 30 min–50 min

Learning Objectives

1. Calculate the shortest path distance between two nodes in a weighted directed graph using Dijkstra's algorithm, justifying each step.
2. Compare the time complexities of Dijkstra's algorithm and the Bellman-Ford algorithm for various graph densities.
3. Evaluate the efficiency of Kruskal's and Prim's algorithms for finding a minimum spanning tree on sparse and dense graphs, providing complexity-based justifications.
4. Explain the greedy-choice property and its role in proving the correctness of Dijkstra's algorithm.
5. Identify and articulate the conditions under which Dijkstra's algorithm fails, specifically the presence of negative edge weights.

Problem-Based Learning

⏱ 30 min·Pairs

Pair Trace: Dijkstra's Walkthrough

Pairs receive printed weighted graphs and colored markers. They trace Dijkstra's priority queue updates step-by-step, recording distances and predecessors. Pairs then swap graphs to verify each other's traces and discuss greedy choices.

Prepare & details

Trace Dijkstra's algorithm on a weighted directed graph, prove its correctness using the greedy-choice property, and explain why it fails when negative edge weights are present.

Facilitation Tip: In Individual Code Challenge: Hybrid Graph, require students to annotate their code with comments explaining each algorithm’s decision point to reinforce conceptual links.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Problem-Based Learning

⏱ 45 min·Small Groups

Small Group Duel: Kruskal vs Prim

Groups get dense and sparse graph handouts. One subgroup implements Kruskal's edge-sorting simulation with string edges, another Prim's vertex-growth with tokens. Groups time their processes and analyze efficiency differences.

Prepare & details

Compare Dijkstra's algorithm and Bellman-Ford in terms of correctness guarantees, time complexity, and the graph properties that determine which should be used.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Problem-Based Learning

⏱ 35 min·Whole Class

Whole Class Relay: Bellman-Ford Iterations

Project a graph; class divides into rows. Front student relaxes one edge per iteration on board, passes marker back. Class checks for convergence or cycles, then codes a simple version together.

Prepare & details

Evaluate the trade-offs between Kruskal's and Prim's algorithms for computing minimum spanning trees, determining which is more efficient for sparse versus dense graphs and justifying the choice using complexity analysis.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Problem-Based Learning

⏱ 50 min·Individual

Individual Code Challenge: Hybrid Graph

Students code Dijkstra's in Python on a starter template with a mixed-weight graph. They add negative edges to test failure, then switch to Bellman-Ford pseudocode. Submit traces with runtime notes.

Prepare & details

Trace Dijkstra's algorithm on a weighted directed graph, prove its correctness using the greedy-choice property, and explain why it fails when negative edge weights are present.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management
• Relationship Skills

Teaching This Topic

Start by having students physically trace paths on paper graphs to build spatial intuition before abstracting to pseudocode. Avoid rushing to formulas; instead, use iterative comparisons of algorithm outputs to reveal why greedy steps or relaxations work. Research shows that students grasp correctness proofs better when they first see the algorithm fail, so design activities where negative edges or dense graphs expose limitations.

What to Expect

Successful learning shows when students can independently trace Dijkstra’s steps, explain why Kruskal’s or Prim’s suits a graph, and justify their algorithm choice with time complexity. Students should also recognize when Dijkstra’s fails and select Bellman-Ford instead.

Watch Out for These Misconceptions

Common Misconception

During Pair Trace: Dijkstra's Walkthrough, watch for students assuming Dijkstra's algorithm can handle negative edge weights because it completes without error.

What to Teach Instead

During the same activity, hand pairs a graph with negative edges and ask them to trace the algorithm. They will observe that finalized distances can be incorrect, prompting a class discussion on why non-negative assumptions are critical.

Common Misconception

During Small Group Duel: Kruskal vs Prim, watch for students confusing minimum spanning trees with shortest path trees.

What to Teach Instead

During the duel, provide each group with tokens to build both structures on the desk, emphasizing that MSTs avoid cycles while path trees follow directed paths from a source.

Common Misconception

During Small Group Duel: Kruskal vs Prim, watch for students believing both algorithms always have identical time complexity.

What to Teach Instead

During the duel, have groups time their implementations on sparse and dense graphs, then compare results to reveal how edge sorting and heap operations impact runtime differently.

Assessment Ideas

Quick Check

After Pair Trace: Dijkstra's Walkthrough, collect each pair’s annotated graph showing distances and predecessors at every step. Assess for correct iteration order and final shortest path output.

Discussion Prompt

During Whole Class Relay: Bellman-Ford Iterations, pause after the first round to ask groups to explain why repeated relaxations are necessary and when a negative cycle would be detected.

Exit Ticket

After Individual Code Challenge: Hybrid Graph, collect students’ algorithm choices and justifications for the given graph types, assessing their ability to connect density to time complexity.

Extensions & Scaffolding

• Challenge students to design a single graph where Dijkstra’s fails and Bellman-Ford succeeds, then write a short explanation of why.
• Scaffolding: Provide pre-labeled graphs with some edges already relaxed or sorted to reduce cognitive load for students struggling with initialization.
• Deeper exploration: Ask students to implement both Kruskal’s and Prim’s using the same graph class to compare data structures and runtime empirically.

Key Vocabulary

Dijkstra's Algorithm	A graph search algorithm that finds the shortest path between a designated start node and all other nodes in a graph, suitable for graphs with non-negative edge weights.
Bellman-Ford Algorithm	An algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted digraph. It can handle graphs with negative edge weights and detect negative cycles.
Minimum Spanning Tree (MST)	A subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Kruskal's Algorithm	A greedy algorithm that finds a minimum spanning tree for a connected, edge-weighted undirected graph by progressively adding edges in increasing order of weight, provided they do not form a cycle.
Prim's Algorithm	A greedy algorithm that finds a minimum spanning tree for a connected, edge-weighted undirected graph. It starts with an arbitrary vertex and grows the tree by adding the cheapest possible connection from the current tree to another vertex.
Greedy-Choice Property	A property of an optimization problem where a globally optimal solution can be arrived at by making a locally optimal (greedy) choice at each step.