Handout 14A

The purpose of this exercise is to study Dijkstra's Algorithm for finding a shortest path in a graph. Parts of this exercise were adapted from examples in Applied Combinatorics with Problem Solving, by Jackson and Thoro.

A graph is a finite collection of vertices with some (or all) pairs of vertices joined by edges. Graphs are commonly used to model air, rail and highway connections between cities, telephone networks, family trees and many other things.

One question that is commonly answered using graphs is "what is the shortest path from this vertex to that one", where travel through the graph is along its edges. An example would be planning the fastest route from one city to another. Here we use Dijkstra's Algorithm to solve such a problem.

The graph below represents the highway network between Potand and Las Vegas. Its edges are weighted with the travel times of each section of highway. Our object is to find the fastest route from Portland to Las Vegas.

Routes and times between Portland and Las Vegas.

You may be able to find the fastest route by trial and error, or by comparing all of the reasonable options. In general, it is faster and more reliable to use a proven algorithm than to figure your route "by hand". Dijkstra's Algorithm is designed for just this application. It works to find the length of the "shortest path" to a vertex in any graph whose edges are labeled with non-negative numbers.

  1. Label your starting vertex zero and label each other vertex infinity (or with an extremely large number.)
  2. Make S be a list of all the vertices of the graph.
  3. Find the vertex V in S with the lowest value label.
  4. Remove vertex V from the list S.
  5. If there are no vertices left in S, stop.
  6. For each vertex in S, replace its label by the lesser of: (In other words, improve the estimate of the time it takes to reach that vertex, if possible.)
  7. Return to step 3.
When you have finished, each vertex will be labeled with a number (assuming that all the vertices are reachable from the starting vertex.) That number represents the minimum sum of edge labels on a path from the start vertex to the labeled vertex. Use Dijkstra's Algorithm to find the minimum time needed to travel from Portland to Las Vegas. Compare your answer with a neighbor's when you're done.

Think of an application of Dijkstra's Algorithm that you might use in teaching a High School class. For instance, you might use the algorithm to find minimum air fares, driving distance, or electrical resistance.

On a separate sheet of paper write a question you would like your students to answer using Dijkstra's Algorithm, draw the graph, and label its edges. Exchange papers with another student in the class. When you have completed each other's problems, discuss them with each other.

If you have time left after the exercise, learn more about Dijkstra's Algorithm by running the applet at http://www.cs.uwa.edu.au/undergraduate/courses/230.300/readings/graphapplet/dijkstra.html or walk through the trace of Dijkstra's Algorithm at http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dij-op.html.

If you're looking for a better description of the algorithm or want to know how to find the fastest route between every pair of cities, check out http://ieng9.ucsd.edu/~mnphan/algorithm/djikstra.html.

Mtht420