Computing · JC 2 · Abstract Data Structures and Algorithms · Semester 1

Shortest Path and Minimum Spanning Tree Algorithms

Students will learn basic debugging techniques to identify and fix errors in their simple programs.

• MOE Syllabus Outcomes
• MOE: Programming - Middle School

About This Topic

Shortest path algorithms, such as Dijkstra's and Bellman-Ford, compute minimal distance paths in weighted graphs. Students trace Dijkstra's steps on directed graphs with non-negative weights, prove its greedy-choice correctness, and note its failure with negative edges. Bellman-Ford relaxes all edges repeatedly to handle negatives and detect cycles. Minimum spanning tree algorithms, Kruskal's and Prim's, connect graphs with minimal total weight: Kruskal's sorts edges by weight, Prim's expands from a starting vertex. Students compare time complexities and select algorithms based on graph density.

In the MOE Computing curriculum's Abstract Data Structures and Algorithms unit, these topics strengthen graph theory application and algorithmic analysis. Students evaluate trade-offs, like O(VE) for Bellman-Ford versus O((V+E) log V) for Dijkstra's with heaps, fostering optimization skills for real-world networks, routing, and logistics.

Active learning benefits this topic through collaborative tracing and coding exercises. Students manipulate graphs physically or digitally, simulate iterations in pairs, and debate choices, which clarifies abstract relaxations and proofs while building debugging confidence.

Key Questions

1. 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.
2. Compare Dijkstra's algorithm and Bellman-Ford in terms of correctness guarantees, time complexity, and the graph properties that determine which should be used.
3. 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.

Learning Objectives

• Calculate the shortest path distance between two nodes in a weighted directed graph using Dijkstra's algorithm, justifying each step.
• Compare the time complexities of Dijkstra's algorithm and the Bellman-Ford algorithm for various graph densities.
• 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.
• Explain the greedy-choice property and its role in proving the correctness of Dijkstra's algorithm.
• Identify and articulate the conditions under which Dijkstra's algorithm fails, specifically the presence of negative edge weights.

Before You Start

Graph Representation (Adjacency Matrix, Adjacency List)

Why: Students need to understand how graphs are represented in memory to effectively implement and trace graph algorithms.

Basic Sorting Algorithms

Why: Kruskal's algorithm relies on sorting edges by weight, so familiarity with sorting is essential.

Introduction to Greedy Algorithms

Why: Understanding the concept of making locally optimal choices is foundational for grasping Prim's and Kruskal's algorithms, and for proving Dijkstra's correctness.

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.

Watch Out for These Misconceptions

Common Misconception

Dijkstra's algorithm works with negative edge weights.

What to Teach Instead

Dijkstra's assumes non-negative weights; negatives cause incorrect greedy selections as distances may decrease later. Tracing iterations on paper in pairs reveals premature finalizations, while coding failures prompt students to explore Bellman-Ford relaxations actively.

Common Misconception

A minimum spanning tree is the same as a shortest path tree.

What to Teach Instead

MST connects all vertices with minimal total weight, no paths specified; shortest path tree minimizes from one source. Group simulations with tokens show MST cycles absence versus path tree's directed structure, clarifying via hands-on builds.

Common Misconception

Kruskal's and Prim's always have the same time complexity.

What to Teach Instead

Kruskal's suits sparse graphs with O(E log E) sorting; Prim's with heaps excels on dense ones at O(E log V). Comparing implementations in small groups on varied graphs highlights density trade-offs through measured runs.

Active Learning Ideas

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.

30 min·Pairs

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.

45 min·Small Groups

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.

35 min·Whole Class

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.

50 min·Individual

Real-World Connections

• Network engineers use shortest path algorithms like Dijkstra's to determine the most efficient routes for data packets across the internet, minimizing latency for users accessing services like Google Search or Netflix.
• Logistics companies, such as UPS or FedEx, employ minimum spanning tree algorithms to optimize the placement of distribution centers and delivery routes, ensuring minimal fuel consumption and delivery times for packages.
• Urban planners and transportation authorities use graph algorithms to design efficient road networks and public transit systems, calculating the shortest travel times between key locations in cities like London or Tokyo.

Assessment Ideas

Quick Check

Provide students with a small weighted directed graph and ask them to manually trace Dijkstra's algorithm to find the shortest path from a given source node. Students should write down the distance and predecessor for each node at each iteration.

Discussion Prompt

Present a scenario with a graph containing negative edge weights. Ask students: 'Why would Dijkstra's algorithm fail here? Which algorithm would be more appropriate, and why?' Facilitate a class discussion comparing the algorithms' strengths and weaknesses.

Exit Ticket

Give students two graph descriptions: one sparse and one dense. Ask them to choose between Kruskal's and Prim's algorithm for finding the MST for each graph, and to briefly justify their choice based on the expected time complexity for that graph type.

Frequently Asked Questions

How do you trace Dijkstra's algorithm on a graph?

Start with source distance zero, use a priority queue for smallest unvisited distance. Relax edges to neighbors, update if shorter, mark visited when dequeued. Students practice on 5-vertex graphs first, verifying with total path sums matching brute force.

What are the key differences between Dijkstra's and Bellman-Ford?

Dijkstra's is faster for non-negative weights via greedy queue; Bellman-Ford iterates V-1 times over all edges for negatives, detects cycles. Teach by contrasting traces: Dijkstra's prunes early, Bellman-Ford exhaustive. Use for routing protocols accordingly.

When should you use Kruskal's versus Prim's for MST?

Kruskal's efficient for sparse graphs due to edge sorting; Prim's better for dense with adjacency lists and heaps. Analyze E/V ratio: sparse E small, prefer Kruskal's. Students justify via big-O on sample graphs, coding both for benchmarks.

How can active learning improve understanding of shortest path algorithms?

Active methods like pair-tracing graphs with manipulatives or relay-coding iterations make relaxations visible and errors immediate. Collaborative debates on greedy choices build proof intuition, while group complexity races connect theory to practice, boosting retention over lectures.