Getting Started

Introductory remarks: Say: 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. But today we’re going to look at a different problem -- the “Shortest Path Problem” -- which is also a widely studied problem in computer science.

Distribute: Worksheet - Intro to the Shortest Path Problem. (Alternative: teacher demonstration)

• Give individual students time to work on finding the shortest paths for the small examples in the worksheet.
  • The worksheet asks students to find the shortest path between two nodes on a series of graphs.
  • Then, students will find the shortest path from one node to all other nodes on the graphs.
• Then pair students to compare their answers.
  • Did you each come up with the shortest path?
  • Was the shortest path always the same?
• Brief share-out.
  • Ask for a volunteer idea for an algorithm.
  • What makes the algorithm harder/easier than minimum spanning tree?
    • Potential responses: easier because you’re told where to start, harder because there is more stuff to keep track of. You need a systematic way to keep track of paths, distances, as you work your way through trying out the nodes.

Wrap-up

Let’s analyze this algorithm.

When we analyze algorithms, there are a few simple questions to ask:

• 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?

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.

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? 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. For the mathematically inclined: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

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?

Activity

Transition: 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). Today we’re going to look at and analyze a famous algorithm that solves this problem.

Instructions:

Say: 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.

Activity Guide: Trace Dijkstra's algorithm on a graph.

Distribute: Dijkstra's Shortest Path Algorithm - Activity Guide

• Give each student one copy of the first page (which contains background info, directions, and the algorithm).
• Give each pair of students one graph diagram to use to trace the algorithm’s progress.
  • There are different 8 diagrams; each is the same graph but with a different source node indicated.
  • Distribute the different diagrams to different pairs of students around the room.
• Students should work in pairs to step through the algorithm and trace it out.
  • Typically one student will read the instructions while the other keeps track of information on the graph diagram.

Give students time to work to trace it out.

Share in small groups.

Once students finish, put pairs together (to make groups of 4).

• 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
• Ask groups to discuss the following:
  • 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?

Assessment

Questions (also in Code Studio):

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

1. 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.

2. 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.

3. 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?

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

Extended Learning

• Dijkstra’s algorithm: http://en.wikipedia.org/wiki/Dijkstra's_algorithm
• Interactive algorithm visualization tool: http://visualgo.net/sssp.html
• A 9-minute lecture on Dijkstra’s algorithm: https://www.youtube.com/watch?v=mv4r7F82doA