Seventh Assignment: Shortest Path
Dave Matuszek, Spring 2003

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.

Details:

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:

Since you will be reading in data from a text file, this program needs to be an application, rather than an applet. 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.

Programming hints:

You will probably want to create a Graph class to support this program. You can use whatever graph representation you think will be most convenient. However, I recommend against creating a complete, general-purpose Graph ADT--just implement the parts you need, as you need them.

For input, you can use my LineReader.java class and a StringTokenizer. For an added challenge (but no extra credit), you might want to try a StreamTokenizer instead.

Due date:

Thursday, April 10.