The problem of the route search is formally defined as the following:

• There is set of points. One of them is marked as the starting point, and the another — as the ending one.
• For every pair of points, A and B, the distance from A to B is defined. The distance may be "infinite" if A and B are not connected directly. The distance from A to B may be not equal to the distance from B to A (like one-way road).
• The route is a subset of points A₁, A₂, A₃, etc, A_N. The route without loops is the route all points of which are unique. (Verify it!) The length of the route is the sum of distances A₁ to A₂, A₂ to A₃, etc, A_N-1 to A_N.
• Let us consider the set of all routes between the starting point A and the ending point B. If any route between these points exist, this set is not empty and, therefore, it has an element with minimal length. Obviously, this is the shortest route we need to find.

The algorithm of the complete review

One of possible strategies is the complete review of all possible routes. If the path exists, it contains no more than N points. That is, the hypothetic algorithm builds a path starting from the point A in all possible directions until the point B is reached or the count of N steps is exceeded.

On the first step, there is potentially N-1 points to review; on the second — N-2 for each of N-1 points, listed on the previous step, etc. As the steps go further, the amount of new branches to review reduces because we forbid loops.

In the worst case, the program will perform (N-1)! cycles. This number grows just a little slower than N^N. In the same time, though, the complete review is the only way to optimize route when shortcuts can change during the pass. That's why almost all strategic games (without pre-calculated solution) implement this algorithm to estimate the series of moves.

The optimized algorithm

Let's return to the problem of finding the optimal route on the static map. Since the shortcuts don't change, there is a solution that takes much less computational resources. As the reader could notice, the previous algorithm will follow a branch, even if the neighboring one already leads into the same place and is shorter. So, the trick is how to cut some branches from the review tree without loss of functionality.

I will describe the short algorithm first and will prove then that it finds the optimal route and calculate how many cycles does it take. Let's use the two-dimensional array A[i,j] that shows the distance from point number i to point number j. Introduce arrays R[i] and L[i]. The array R[i] contains the number of point that is before the point number i in the route that is currently being reviewed. L[i] contains the length of this route, from the starting point to the point number i.

The program performs N steps. On each step, the list of currently reviewed points is maintained. By its meaning, this list is analogous to the wave on water surface from a dropped stone. On the first step, the list contains only the starting point, in the second — points that can be reached directly from it... In further steps, the list will contain points that can be reached from the points listed on the previous step.

So far, it looks like the complete review of routes described above. But now we put a restriction in the process of listing. On each step, program remembers the shortest distance from the starting point to the point being reviewed (array L), and the back route from it (array R). When a point is to be added to the list (of next step), the program verifies whether another route exist, and is it shorter than the current route.

It can be done by comparing the value of L[i], where i is the number of point being added, with the actual length of the new route L[j]+A[j,i], where j is the previous point in the current route.

If the new route to the point number i is shorter, the program puts new distance to the L[i] and the new back direction to the R[i]. Otherwise, this route is removed from further consideration. Also, the program has to guarantee that each point is listed only once (i.e. verify whether the point is already listed). Try to suggest an algorithm of such a verification that doesn't perform any cycle, before reading the answer.

This procedure will remove from consideration only routes that are longer. In other words, if a route to the certain point is removed, there is another route to this point and it is shorter. Therefore, the shortest route will never be deleted.

Finally, let's calculate the number of cycles program needs to find a route. Since the total number of steps is N and there is no more than N points is reviewed on each, the total number of cycles is no more than N². Furthermore, if the number of shortcuts going from a point is limited (such as for 2D maze), the number of cycles grows as N¹ as N increases. I leave the proof of this fact to my reader.