Introduction.
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.