CIT 594 Assignment 7: Shortest Path
Spring 2010, David Matuszek

Purpose of the assignment

The general idea

Write a program that finds the shortest distance between two towns, using Dijkstra's algorithm.

The algorithm

See my PowerPoint lecture on graphs.


Read in, from a text file, a list of town-distance-town triplets, one triplet per line. For example, for this map, you would read in:

Audlum 8 Bidville
Bidville 10 Clarion
Bidville 8 Drongo
Clarion 15 Drongo
Drongo 12 Eastwick
Bidville 8 Fanfair

You can assume:

So that I can test your program with other data, use the data format exactly as described above, and use a dialog box to select the input file.(The little map above is not sufficient to give your program a good test.)

Please use a GUI for this program. The GUI doesn't have to be fancy, but it should be self-explanatory.

Create a Graph class to support this program. You can use whatever graph representation you think will be most convenient. You need not create a complete Graph API, just the parts you need; but do keep your Graph class separate from the class that solves this particular problem.

Due date

Thursday, April 15.