SUNY Geneseo Department of Computer Science

Problem Set 10—Dijkstra’s Algorithm

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Wednesday, April 3

Purpose

This problem set increases your understanding of Dijkstra’s algorithm for finding shortest paths in graphs.

Background

Dijkstra’s algorithm is a widely-used one for finding shortest paths through a graph from a fixed starting vertex to all other vertices. It is described in section 24.3 of our textbook (with some supporting material in section 24.1), and we discussed it in class on March 28.

Exercise

Solve the following problems:

Problem 1

This problem examines the problems that negative-weight edges cause for Dijkstra’s algorithm.

Part A. Give an example of a graph with a negative-weight edge but well-defined shortest paths in which an (attempted) execution of Dijkstra’s algorithm fails to find a shortest path because of the negative-weight edge. Show enough of the execution of the algorithm to demonstrate how it fails.

Part B. Give an example of a graph with a negative-weight edge but well-defined shortest paths in which an execution of Dijkstra’s algorithm successfully finds all shortest paths from the source vertex despite the negative-weight edge.

Problem 2

Code Dijkstra’s algorithm in a program and demonstrate that it works.

To help you test your program, I have provided two text files that contain simple graphs. Both graphs represent maps; vertices represent intersections between roads and edges represent a road between two intersections. Both graphs are undirected but weighted. The first is a description of selected street intersections in Geneseo, with weights being approximate distances between intersections, in feet. This map doesn’t know about all the streets in Geneseo, and knows next to nothing about the College. You are free to extend it on your own if you want. The second map is a map of hypothetical train routes between New York City and Chattanooga, Tennessee (I got it at a conference I was once at in Chattanooga). The weights in this map are hypothetical dollar costs of tickets between cities.

Both files have the same format, as follows:

The files have two sections
The first section consists of lines that describe map locations (i.e., vertices in the graph). Each line contains an integer ID number for the location (e.g., 0), followed by a space. Everything after the space is text describing the location (e.g., “Main St & Rt 20A”).
ID numbers for locations are consecutive integers, starting at 0.
The end of the first section is marked by a line that looks like a location, except that the ID number is 99999 and the description is the word “Separator.” No other location has either this ID number or this description.
Each line in the second section contains three integers, separated by spaces. The first two integers are ID numbers for locations, and the third number is the cost of traveling between those locations. Depending on the map, costs may be distances, dollar costs of tickets or tolls, etc. For example, the entry “0 1 308” means that there is a road (or piece of road) between locations 0 and 1, and that road has a cost of 308. Note that each of these lines defines an undirected edge and its weight in the graph.
The second section continues from the separator line to the end of the file.

Both files are available from the “Exercises” Web page for this course. I don’t care how (or even if) you read these files into your program. The files are designed to be fairly easy for a program to parse, but if you wish you can just put the information from the files into your program by hand, or can test your program on other graphs of your own devising.

I similarly don’t care what the user interface to your program looks like. In particular, you are free to get the starting vertex for finding shortest paths in any manner you want, and to display the results in any form.

You may write the program in any language you like.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to problem 1 this meeting. Also bring a version of your program for problem 2 that I can both read and run. The easiest way to do this will be to bring the program on your own laptop computer.

Meetings should take about 15 minutes. Please sign up for your meeting on the schedule outside my office, or via Google Calendar. If you work in a group, the entire group can schedule a single meeting with me. Your meeting should end by the end of the due date above.