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.