Knight's shortest path graph data structure and algorithm

Question

I have a question on one of the previous Stack Overflow post @ Knight's Shortest Path on Chessboard

I understand the reply on 'ok, it's a graph question, and its sparse matrix is like':

(a1,b3)=1,
(a1,c2)=1,
  .....

which describe existing edges. However i still don't know what Data Structure of this Graph should looks like (is it an adjacency matrix? stated as 'sparse matrix' above, or something else?), so that it can be readily used by Dijkstra's algorithm.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.

From the algorithm description, it looks convenient if the graph data structure is a set of vertex, with neighbor vertex information available. But how do we achieve this?

How can I write out a sample data structure for this graph? I am seeking an understanding of how it can be linked conveniently to Dijkstra's algorithm.

Answer 1

The graph is very sparse (64 vertices, each vertex has at most 8 edges) thus an adjacency matrix is a waste IMO.

A better structure for this will be adjacency list:

v1->v2,v3,v4,v5
v2->v1,...
...

The idea is indeed to hold a Set<Vertex>, and for the Vertex type to have a field: List<Vertex> neighbors, which will contain all the vertex's neighboring vertices.

There is no need in this case for some additional weight information - since the graph is unweighted.

Also - Dijkstra's algorithm is redundant in here. Again, the graph is unweighted - so a simpler (to program and understand) and faster (run time) algorithm to find the shortest path is a BFS for unweighted graphs.

Answer 2

Since there are only 64 tiles, you can conveniently put the adjacency matrix in an array of 64 integers of 64 bits each. Sure it's sparse, but it's also tiny, so the waste, if it exists at all (pointers are pretty big compared to single bits), will be small too.

Extracting a list of indices from a bitvector is also especially easy when it's sparse, but you don't even need that - you could let the front be a queue of bitvectors instead, and the "already visited" set could be a single bitvector.

edit: ok actually you may still need it if you use that trick, but then it remains that it just takes a couple of fast operations such as bitscan and x &= x -1.