# 图搜索代写 | Assignment 09: Graph Searching [cse30s21]

Assignment
You shall write a Python program that calculates and prints the shortest path between two vertices in our e-roads graph.
1. You may deﬁne multiple modules if you’d like, but name your main module cse30_e_roads. You may want to use your Graph class from Assignment 08, but
defaultdict(dict) will work just as well since this graph need not support deletion.
2. Expect at least two command-line arguments as names of a starting city and an ending city , respectively .
3. If either city name does not exist in the dataset, or there is no path between the two cities, print an informative one-line message to standard error (sys.stderr
[https://docs.python.org/3/library/sys.html#sys.stderr]) and exit with a nonzero exit status (sys.exit
[https://docs.python.org/3/library/sys.html#sys.exit]).

4. If only two command-line arguments are provided, print, to standard output, one per line, the name of each city along the shortest path (start to ﬁnish).
In order to determine the shortest path, assign weights to each edge that represent the great-circle distance [https://en.wikipedia.org/wiki/Great-circle_distance] between
the two geographic coordinates as per the haversine formula [https://en.wikipedia.org/wiki/Haversine_formula]. Feel free to port and cite the JavaScript code on this
site [https://www.movable-type.co.uk/scripts/latlong.html] (it translates almost directly to Python).
5. If a third command-line argument exists, print a Google Maps URL requesting directions between the vertex coordinates, instead of the names of the cities.
The format of the URL is fairly straightforward:
Round the coordinates to three digits after the decimal point to keep the URL length from getting too unwieldy , as in the example given above