The file miles.dat contains basic geographic data on 128 cities in North America. This homework asks you to write a program that reads miles.dat and then efficiently responds to shortest path queries about the data. Specifically, miles.dat contains, for each city, the following pieces of information:
Building Graphs. From this data, we can build a variety of graphs depending on the specific application. For this homework, I want you to build a graph whose vertices are the 128 cities and whose edges connect pairs or cities that are at most 400 miles apart. If city x and city y are at most 400 miles apart, then you should associate with the edge between city x and city y the distance between these two cities. Also, each city has a few attributes such as its state, longitude and latitude, and population that you should store in the graph data structure. You should think about how to (slightly) modify the graph data structure discussed in class, to store this additional information.
Computing shortest paths. You program should contain a function, with the following header:
def shortestPath(graph, source, dest)that computes and returns a shortest path from the vertex source to the vertex dest. We will be discussing Dijkstra's shortest path algorithm in class and I will also provide most of the code for this.
Outputing a kml file.
To visualize the shortest paths produced by your computations, you should write a function that takes our graph, a path in this graph, and produces a corresponding kml file that can be viewed in Google Maps or Microsoft LiveSearch Maps. Here is the tutorial I used to learn about kml files: kml Tutorial. Here is a sample kml file that I made using a little bit of the data from miles.dat and here is what you see when you view the kml file on Microsoft's LiveSearch Maps.
Things you should do.
To a larges extent, your program will be judged on the correctness of the following functions:
What to submit.
A python progam called hw10.py along with a corresponding README file.