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

# Purpose of the assignment

• To give you experience with graphs

# 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.

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 (see SwingExamples.jar).
• Provide a way to choose two towns.
• Display (as text) the shortest path between those two towns, in the correct order.

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.