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.
Students will be able to:
- Reason about a general solution (algorithm) for a problem while examining specific instances of it
- Informally analyze an algorithm to state how "long" it takes to run relative to the size of the problem
- Follow a pseudocode algorithm for the single source shortest path problem
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.
- Worksheet - Intro to the Shortest Path Problem in large print
- Worksheet - Intro to the Shortest Path Problem in braille, Duxbury file
- Worksheet - Intro to the Shortest Path Problem in braille, .brf
- Activity Guide in large print
- Activity Guide in braille, Duxbury file
- Activity Guide in braille, .brf
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.
- In pairs, did you each come up with the shortest path?
- Was the shortest path always the same?
- What makes the algorithm harder or easier than the minimum spanning tree?
- Work as a group, if you'd like, on the first page, but try to have students try the second page on their own.
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.
- Compare the shortest path diagrams; these form a tree extending from the source node.
- Are the shortest path trees from two different sources the same?
- What about the path between the two source nodes? (for example: in group A, is their path to E the same as E to A?) If so, why? If not, why not?
- Based on your experience, would this algorithm find the shortest path for any graph of nodes and edges?
- Is there a way to stop early? That is, is there a way to stop processing the algorithm because you know you've found the shortest path tree? Can you guarantee that you could always stop early? Why or why not?
It's more interesting if you groups pairs based on which diagrams they were assigned. Here is a suggestion:
- Graph A with Graph E
- Graph B with Graph F
- Graph C with Graph H
- Graph D with Graph G
When analyzing algorithms, ask these three questions:
- Is it correct? Will it always solve the problem with a correct solution?
- How much time does it take to run? (Even correct and efficient algorithms take different amounts of time)
- Will it run in a "reasonable" amount of time; is it efficient?
1. Is it correct?
- Yes. Beyond intuition, there is a mathematical proof that Dijkstra's algorithm is correct (if all edge weights are positive) and will always find the Shortest Path Spanning Tree for the given source node
2. How much time does it take to run?
- Time is an interesting element when talking about computer algorithms. Because there are so many different types of machines with different processing speeds, it's not really useful to talk about the amount of time an algorithm takes to run in terms of "clock time," since it will be different on every computer.
- A better indicator is to think about how many "things" the algorithm is making the computer do to run to completion: arithmetic operations, updates to memory, etc. The most important things are those that get performed repeatedly as part of the algorithm. In the shortest path problem, we have to do some processing of every node and every edge. So the shortest path problem is dependent on the total number of nodes and edges in the graph.
- With the minimum spanning tree problem, we created a tree, but it was possible (if not likely) that we didn't even need to consider every edge in the graph. So with MST, it was dependent on the number of nodes and edges, but we could stop after we found n-1 edges. This is a potential factor when thinking about time.
- Note: there are graphs for which the MST has to consider every edge. It has the same theoretical running time in the worst case as SSSP.
- What about the shortest path tree? Is there anyway to stop early? Possibly when are you done?
- For Shortest Path you can only stop after you have processed every edge. You cannot stop early. When running the algorithm, it is possible that the very last edge might cause a path to change. Thus, we might say the amount of "time" it takes to run this algorithm is proportional to the amount of time it takes visit every node and every edge once.
- Note: Technically, the running time for Dijkstra's is a little bit more than than just V+E (the number of vertices plus the number of edges). There are computing costs associated with searching for the node that contains the next smallest total distance.
3. Is it efficient?
- This algorithm is actually pretty efficient. Discovering the shortest path tree for a node, by looking at every node and edge just once, intuitively feels like you can't do much better; how could you know the paths without looking at all the edges? Some algorithms on graphs require you to process nodes and edges multiple times. As an easy example to think about: what if we wanted a computer not to find the single source shortest path, but find the ALL the shortest path trees?
1. Which one of the diagrams below shows the shortest path tree from the source node indicated.
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.
- Graph 1 Connections: A-E, B-E, C-D, D-E
- Graph 2 Connections: A-E, B-C, C-D, D-E
- Graph 3 Connections: A-B, A-E, A-D, C-E
- Graph 4 Connections: A-D, B-E, C-D, D-E
- Graph 5 Connections: A-E, B-E, C-E, D-E
2. Which of the following statements is FALSE about minimum spanning trees (from the previous lesson) and shortest path trees:
- A. The minimum spanning tree algorithm you learned does not necessarily need to try every edge.
- B. A minimum spanning tree contains the shortest path between the starting vertex and every other reachable vertex in the graph.
- C. The shortest path algorithm you learned visits each vertex and edge once.
- D. Both the minimum spanning tree algorithm you learned and the shortest path algorithm you learned used a "greedy" approach, choosing the smallest edge first or vertex with the smallest distance value first.
3. Which of the following is NOT something we are concerned with when we write an algorithm?
- A. The algorithm is short.
- B. The algorithm is correct.
- C. The algorithm is efficient.
- D. The algorithm is understandable.
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?"
- CSTA K-12 Computer Science Standards (2011): CT.L3B:3, CT.L3B:4, CT.L3B:6
- Computer Science Principles: 4.1.2 (A, B, C)
- Computer Science Principles: 4.2.1 (A, B)
- Computer Science Principles: 4.2.4 (A, B, C, D, G)