Question Detail: So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10×10 pattern (think chessboard). The graph is undirected, and unweighted. Moving through the graph involves moving three spaces forward and one space to either right or left (similar to how a chess knight moves across a board). Given a fixed beginning node, how would one find the shortest path to any other node on the board? I imagined that there would only be an edge between nodes that are viable moves. So, given this information, I would want to find the shortest path from a starting node to an ending node. My initial thought was that each edge is weighted with weight 1. However, the graph is undirected, so Djikstras would not be an ideal fit. Therefore, I decided to do it using an altered form of a depth first search. However, I couldn’t for the life of me visualize how to get the shortest path using the search. Another thing I tried was putting the graph in tree form with the starting node as the root, and then selecting the shallowest (lowest row number) result that gave me the desired end node… this worked, but was incredibly inefficient, and thus would not work for a larger graph. Does anyone have any ideas that might point me in the right direction on this one? Thank you very much. (I tried to put in a visualization of the graph, but was unable to due to my low reputation)
Asked By : gfppaste
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1329
Answered By : Nicholas Mancuso
If the edges in the graph only represent valid moves between certain positions, using Dijkstra’s would work just fine. However as the graph is unweighted it would be overkill. A simple breadth-first-search will give the optimal answer.
