User:LunaticFringe/Shortest path

There are many programming questions which are based on finding the shortest path between two or more nodes. For example, you could be given a list of n cities, along with a list of one- or two-way roads (start city, end city, length of road). You could then be asked to find all shortest paths between city A and city B, or to find the first lexicographical shortest path, or simply to find the length of the shortest path.

With many problems, however, the underlying graph construction is not so obvious. Imagine a 3x3 "moving squares" puzzle in which you must horizontally and vertically move the tiles to unscramble the picture. A problem could ask whether or not it was possible to win the game from a given starting position, and if so, to return the fewest number of moves necessary. In this example, the various alignments of the puzzle are the nodes; an edge between two nodes indicates that you can get from one state to the other in a single move.

Strategy

When you suspect a question to be a Shortest Path problem, there are two questions to ask. First of all, is the distance between states always the same? In the puzzle example above, every edge has a value of 1, indicating that it takes one move to get from node x to node y. On the other hand, distance is important in the city and road example. If edge distances vary, the solution of this problem will involve a data structure known as a Priority Queue. If the edges are uniform, however, the problem can be solved using a much simpler Breadth First Search.

Secondly, it is important to know if you need only calculate the distance from one node to another, or if the shortest paths themselves must be found. The former takes less code and less memory to find than the latter.