|Seventh Assignment: Shortest Path
Dave Matuszek, Spring 2003
Write a program that finds the shortest distance between two towns, using Dijkstra's 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:
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.
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
class and a
StringTokenizer. For an added challenge (but no extra
credit), you might want to try a
Thursday, April 10.