[Python] Find the shortest distance between two squares on a game board

I have the paths on a game board stored in a dictionary formatted something like the following:

{1: [2,3,4], 2: [1,3,5], 3: [1,2,4], ...}


This means if you're on space 1, you can move to spaces 2, 3, or 4, and so on. Every key links to at least two values in the list; many have four or more. There are 199 total spaces on the board. A notable catch is that sometimes you might be able to skip a space, so in...

{1:[2,3,4], 2:[3]}


...you can go 1 -> 2 -> 3, or you can just go 1 -> 3.

I'm looking to create an algorithm to find the shortest distance between any two squares. The obvious thought is to look up the key for the starting space, then take the first number in the list, look up the possible spaces for that, and so on, stopping and returning to the previous list when it hits either a previously seen number or the final square (storing the path and distance if it hits the result square, to be compared after finishing).

I have very little idea about how to start implementing this, though. (If there were only two steps, I'd use nested loops, but obviously that won't work here, since I don't know how many levels deep it might go).

Better solutions or optimizations involving other data structures are welcome; I have the data stored in a CSV file resembling this dictionary, so I can easily convert it to something else if that would work better.

Here's a link to a picture of the board I'm working with:

EDIT: Okay, I'm trying to implement Dijkstra's algorithm. Here's what I've got:

1 movedict, transdict = boardstruct.prepare_board()
2
3 source = 87
4 dest = 88
5
6 dist = {}
7 prev = {}
8 for v in movedict.keys():
9 dist[v] = float('inf')
10 prev[v] = None
11
12 dist[source] = 0
13 q = movedict.keys()
14
15 while q:
16 smallest = float('inf')
17 for i in q:
18 dist_to = dist
19 if dist_to < smallest:
20 smallest = dist_to
21 print smallest
22 u = q.pop(smallest)
23 print u
24
25 if dist == float('inf'):
26 break
27
28 for v in movedict:
29 alt = dist + 1 # distance = flat 1
30 if alt < dist[v]:
31 dist[v] = alt
32 prev[v] = u
33 # reorder queue?


(21 and 23 are debug statements I forgot to remove)

I'm working off pseudocode from Wikipedia (http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode), as I can't find any existing implementations that match a data format like what I need (every move has a fixed cost, so the distance is not stored anywhere).

I understand I need to reorder the queue at the end, but I'm not sure how. I also don't understand what lines 25 and 26 are for (the comment says "all remaining vertices are inaccessible from source"--does this just keep it from running any further when it's guaranteed to have already found the best path?). I probably messed something else up, too, so if you could look over it I'd appreciate it.

Continue reading...