Overview

This lesson explores the Single Source Shortest Path problem, by solving the problem with pencil and paper first, then by following a famous algorithm that solves the shortest path problem known as Dijkstra's Algorithm. Even though this is an algorithms detour, there is a strong connection in this lesson to routing algorithms used on the Internet. This lesson also introduces ideas about how we analyze algorithms: looking for correctness, efficiency and running time.

Goals

Students will be able to:

Purpose

Algorithms for the Shortest Path Problem have many applications and it's a widely studied class of problems in Computer Science. The web abounds with video lectures and presentations about it. Dijkstra's algorithm, which you will follow in this lesson, is one of the most famous shortest path algorithms. While shortest path algorithms are not required knowledge for Computer Science Principles, understanding how algorithms are expressed, and being able to reason about and informally analyze algorithms is. This lesson should set a good foundation for the aspects of expressing and analyzing algorithms that make them challenging and interesting.

Resources

Getting Started

In the previous lesson you developed an algorithm for the Minimum Spanning Tree (MST) problem. The MST is useful for knowing the most cost-effective way to build or connect a network together. This lesson looks at a different problem, the "Shortest Path Problem" - which is also a widely studied problem in computer science. Look at the short questions on the worksheet, and try to finish the shortest distance between the nodes.

Give individual students time to work on the Intro to the Shortest Path Problem Worksheet. Have them start with the small examples in the worksheet, then pair students up to compare their answers. Then discuss the following.

Pro Tip

Activity

The reason we have routers is because we want to send messages from our router to lots and lots of different locations. So a more interesting problem on the Internet is finding not just the path from my router to one other router, but the path from my router to EVERY other router!

This is known as the Single Source Shortest Path Problem (SSSP). This activity looks at and analyzes a famous algorithm that solves this problem.

You and your partner will be given the algorithm and a graph. And together you will act as the computer, interpreting the instructions and trying to trace out the algorithm and follow its steps.

Part of analyzing an algorithm is trying it out on many different inputs. So, each group will have a different node to start with on the graph and we will test the algorithm to see if it works and then see what we think about it, in terms of its correctness and efficiency.

Each student should receive a copy of the first page of the Activity Guide, but each pair of students only needs one of the eight graph diagrams to trace the algorithm. Try to distribute the different diagrams to different pairs of students in a relatively even manner.

When students are done, have them pair up with another group to compare results. Have groups discuss the following topics.

Pro Tip

It's more interesting if you groups pairs based on which diagrams they were assigned. Here is a suggestion:

Wrap Up

When analyzing algorithms, ask these three questions:

1. Is it correct?

2. How much time does it take to run?

3. Is it efficient?

Assessment

1. Which one of the diagrams below shows the shortest path tree from the source node indicated.

Assessment Question 1 - Diagram

Teacher's Tip: Diagram Description

The diagram above contains five identical graphs. Each graph consists of four nodes connected in a circular fashion, "A," "B," "C," and "D," and a final node in the middle, "E." The source node is "A," and the connections' values are available in the Connection List (link). Each graph has different connections highlighted, as follows.

2. Which of the following statements is FALSE about minimum spanning trees (from the previous lesson) and shortest path trees:

3. Which of the following is NOT something we are concerned with when we write an algorithm?

4. If a graph has 10 nodes and 33 edges, how many nodes and edges will be visited/processed as a result of running Dijkstra's algorithm?

5. When analyzing algorithms, why doesn't the amount of real time (clock time) tell us very much about the algorithm's "efficiency?"

Extended Learning


Standards Alignment