CSC 210 Program #5

Shortcut

Logistics

Go...

•  Worth 4 points, or 4% of your class grade
•  Assigned Saturday May 13, 2006
•  Due Saturday May 27, 2006 by the end of the day
•  Covers graphs, Dijkstra's Algorithm

Description

Please implement Dijkstra's Algorithm to find the shortest path in a graph. Input to the algorithm is a starting vertex. The output is the shortest path to all the remaining vertices in the graph. Yes. It is cool.

Implementation

Implementation details:

•  Please implement an adjacency matrix flavor of the Graph interface. If you want to change (or more specifically, improve) the book's Graph interface, feel free.
•  Please be able to handle directed and undirected graphs. As our text points out, undirected graphs can be handled by adding edges for each direction to your graph.
•  Please be able to handle vertex names either in your Graph class or as a separate table lookup. I would like to see paths reported using the nice vertex names that you'll read in from a file (see below).
•  Make at least one speed or memory tweak/improvement to the ideas given in our textbook, section 12.6. We'll talk about this in class.
• As far as your user interface:
  1.  Read in a graph from a file
  2.  Ask the user for a start vertex and an end vertex
  3.  Print the shortest path (each vertex and weight) from the start to the end

Examples/Files

I'll provide some graph examples (files) for you to munge. The format is:

An example (from page 670 of our textbook) is:

•  Attached to this hardcopy,
•  on the k: drive, and
•  right here: page670_cities.txt

I will create more examples for you over the course of the next week.

Grading

You know the drill by now, eh.

By the due date, please place your work for Program #5 in your folder on the k: drive. I'll be looking for:

•  A README file describing the state of your program... what works, what doesn't, etc.
•  All your *.java Java source code files
•  All your *.class files... please compile your Java
•  A javadoc folder with the nifty auto-magic documentation of your classes

Of course, your code must be beautiful and follow the class coding guidelines. Code that does not meet this metric will be served a harsh brand of grading justice.

Etc

Hey, if you like graphics, you can do programming problem 12.7 on page 677 instead.

Hey (again), look at this fun interactive Dijkstra from some Japanese guy:

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

May 20, 2006

Hey guys, I have slightly modified the file format. It's very straightforward... here are some samples for you:

•  program05\page670_cities.txt - example from our text, page 270
•  program05\aho_ullman_page205.txt - example from my old Aho & Ullman text, page 205
•  program05\japan1.txt - a 9x15 example from the Japanese guy's site above
•  program05\japan2.txt - a 48x77 example from the same guy

Also, here's my Java to read this format: program05/Program05Prep.java

Please note that the japan2 file references nodes by number in the .edges section. I haven' coded that up in my reader yet.

Everything's on the k: drive as well.

good luck... yow, bill