Pathfinding

Template: Click this link, and share with mrcodeswildride: new project

Technique

Use backtracking. Every backtracking problem has a base case and recursive case.
The base case is when the result can be computed directly. For this project, the base case is when the starting city and destination city are the same. The shortest path is simply zero.
The recursive case is when the result must be computed by breaking down the problem into smaller problems. For this project, the recursive case is when the starting city and destination city aren't the same. The shortest path is computed by following every path from the starting city and running the same procedure again until the base case is reached. This is called graph traversal.
Make a function that takes a starting city and destination city as parameters, and have that function call itself for the recursive case, passing the next city in the path as the starting city parameter. Eventually, either the base case will be reached, or the path will end. In either case, backtrack to find another path until all paths are found.

Hints

For storing the connections between cities, make an object for each connection.
Last section Next section