Index of /~baker/pc/city

[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory   -  
[ ]dijkstra.ppt 2009-04-23 22:08 337K 
[ ]dijkstra.pdf 2009-04-23 22:08 250K 
[ ]fsu0409contest.pdf 2009-04-23 14:23 57K 
[TXT]City.java 2009-04-23 22:09 4.6K 
[TXT]DTree.java 2009-04-22 21:39 3.3K 
[ ]Makefile 2009-04-22 21:38 331  
[ ]out2 2009-04-22 21:38 69  
[ ]in2.out 2009-04-22 21:38 69  
[ ]in3.out 2009-04-22 21:38 47  
[ ]out4 2009-04-22 21:38 30  
[ ]in4.out 2009-04-22 21:38 30  
[ ]out3 2009-04-22 21:38 29  
[ ]out0 2009-04-22 21:38 28  
[ ]in0.out 2009-04-22 21:38 28  
[ ]out1 2009-04-22 21:38 21  
[ ]in1.out 2009-04-22 21:38 21  
[ ]in3 2009-04-22 21:38 10  
[ ]in4 2009-04-22 21:38 9  
[ ]in2 2009-04-22 21:38 9  
[ ]in1 2009-04-22 21:38 9  
[ ]data2 2009-04-21 12:47 9  
[ ]data1 2009-04-21 12:47 9  
[ ]in0 2009-04-22 21:38 8  
[DIR]going/ 2009-04-21 19:45 -  

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.