Index of /~baker/pc/city

[ICO]NameLast modifiedSizeDescription

[DIR]Parent Directory  -
[TXT]City.java23-Apr-2009 22:09 4.6K
[TXT]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
[DIR]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.