# Index of /~baker/pc/city

Parent Directory  -
City.java23-Apr-2009 22:09 4.6K
DTree.java22-Apr-2009 21:39 3.3K
Makefile22-Apr-2009 21:38 331
data121-Apr-2009 12:47 9
data221-Apr-2009 12:47 9
dijkstra.pdf23-Apr-2009 22:08 250K
dijkstra.ppt23-Apr-2009 22:08 337K
fsu0409contest.pdf23-Apr-2009 14:23 57K
going/21-Apr-2009 19:45 -
in022-Apr-2009 21:38 8
in0.out22-Apr-2009 21:38 28
in122-Apr-2009 21:38 9
in1.out22-Apr-2009 21:38 21
in222-Apr-2009 21:38 9
in2.out22-Apr-2009 21:38 69
in322-Apr-2009 21:38 10
in3.out22-Apr-2009 21:38 47
in422-Apr-2009 21:38 9
in4.out22-Apr-2009 21:38 30
out022-Apr-2009 21:38 28
out122-Apr-2009 21:38 21
out222-Apr-2009 21:38 69
out322-Apr-2009 21:38 29
out422-Apr-2009 21:38 30

This is my attemnpt at a solution to Problem 6 of the spring 2009 FSU ACM local programming contest (see fsu0409contest.pdf). I picked this as an example of a problem that might be solved using Dijkstra's shortest-path algorithm.

Unfornately, the original problem statement has errors in it. The examples in the problem statement do not match the verbal description of the problem. To resole these inconsistencies, I first assumed that the intent was for the computations of neighbors be done mod 4 rather than mod N. Even at that, there was no path for the proposed example input. So, I assumed further that all edges of the graph are bidirectional. With that, I was able to match the judge's sample output for all but set in4. I believe that dataset is just wrong.

Regardless of the problems with the question and the Judge's sample data, this is still a valid application of Dijkstra's algorithm.

For fun, I tried coding solutions to this in several ways, including one using the standard java.utilities.PriorityQueue and one using a priority queue of my own (DTree.java).

The Java code of my solution using java.utilizies.PriorityQueue is in City.java.