Navigation by searching a graph (part 2) [20 points]

The goal of this assignment is to develop your own program to run graph searching algorithms. The program needs to use a graph representing a 2D map of some area, consisting of nodes, corresponding to places on the map, and edges, corresponding to roads connecting the map places. The places will have specific 2D spatial coordinates, and the edges will have costs, corresponding to travel distances between the places.

Your first task will be to locate a library of AI graph searching procedures for the programming language of your choice. Then write a program to use this library to allow the user to find the shortest (or any, depending on the graph searching algorithm selected by the user) path between the selected starting point and destination, and dispay this path as a sequence of places.

Do not worry about a fancy user interface. The simple sequence of questions (start, destination, search algorithm) is perfectly sufficient.

You can create a graph using some program (even the AISpace graph searching applet), or you can create it with a text editor. All the connections should have distances specified going each way. Make sure your grah is not too small or trivial, so that you can make meaningful searches on it. Approximately 20 nodes, with at least several paths connecting most of the nodes should provide a rich enough environment to test searching algorithms.

Also, think about some way to provide a heuristic for the navigation. A simple and useful heuristic can be obtained by measuring the geometric distance between two nodes. But in order to be able to use it, your graph nodes would have to have geometric coordinates.