Purpose of the assignment:

• To give you more experience with data structures (graphs in particular).

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:

• There will be fewer than 100 towns.
• Every town has a unique, one-word name.
• At most one road will connect any pair of towns.
• Distances are given in small positive integers.
• All roads are bidirectional, and the distance is the same in either direction (that is, the map is an undirected graph).
• The map is connected; that is, you can get from any town to any other town.

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.

• Display the input data in a scrolling text area.
• Provide a way to choose two towns (where to start from and where to finish at).
• Display the shortest path between those two towns, in the correct order.

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.