Single Origin Shortest Paths

Depth First Search (https://xkcd.com/761/)

Github Classroom

You can clone the starter files for this lab at this GitHub Classroom link. Be sure to open the assignment in VSCode and setup up your virtual environment following these instructions.

In this lab, you will use a shortest-paths algorithm to help users find the shortest path between two points in a map! Your main task will be to implement Dijkstra’s algorithm using a DirectedGraph structure similar to one discussed in class.

Directed Graphs

Recall from class that a directed graph is a graph where each arc (aka directed edge) has a source and destination vertex, which we call tail and head, respectively.

Our directed graph will have the following representation:

A list of nodes
A list of directed edges
For each edge, a dart (e, True), and (e, False)
A procedure dart2head, which, given a dart, returns its head
A procedure head2darts, which, given a node, returns the darts which have that node as their head

We have also given several helper functions in shorteset_path.py which will be useful for working with this graph representation.

Task: Check out the Graph class in directed_graph.py, and familiarize yourself with its structure.

Road Networks

Now, consider a road network, which is a directed graph where each node represents an intersection and each arc represents a road segment.

If you want to find the shortest path between two intersections, you can use a shortest-paths algorithm to find the shortest path from the source intersection to all other intersections. Note that here, our definition of shortest is based on the length of the road segments, but this approach is generalizable to other metrics (or costs) for each arc on the graph, such as the time it takes to traverse each road segment, or the number of road segments that you traverse (number of arcs).

You will able to use your shortest-paths algorithm to answer all of these queries.

Shortest Paths

Your main task is to implement Dijkstra’s algorithm to find the shortest path between two nodes in a directed graph.

You are provided as a parameter a cost_function that takes an edge and returns the cost of that edge. This can be used to re-use your shortest paths code for different cost functions, such as the lengths of the road segments, the time it takes to traverse each road segment, or the number of road segments that you traverse (number of arcs).

Task: Implement the shortest_path function in shortest_path.py to find the shortest path between two nodes in a directed graph using Dijkstra’s algorithm.

Hint: You can use Python’s built-in PriorityQueue as a priority queue for your search!

Checkpoint: Test your implementation by running the road_network.py file!

You can run python road_network.py to run your shortest paths algorithm to find the shortest path between Providence Place Mall and the Roger Williams zoo.

If you want to test your implementation with different queries, you can check out the additional parameters at:

python road_network.py --help

Specifically, try running the following command to find different shortest paths for different metrics:

python road_network.py --cost time length edges

Check in with a TA and show them your solution!

A* Search

By modifying our cost function with a “good” (admissible) heuristic function, we may be able to speedup our shortest_path implementation! This is typically known as A* search. We’ll be using the Haversine distance from our current position to the destination as a lower-bound for the distance required to reach the destination.

This heuristic is specifically designed for geometric distances. Therefore, it only makes sense to use this heuristic when working with the length cost function.

Task: In heuristic_shortest_path.py, finish implementing shortest_path_with_Astar. Given a cost function $\rho$ , your modified cost function should be given by

\rho'(a) = \rho(a) - \text{haversine\_distance}(\text{tail}(a)) + \text{haversine\_distance}(\text{head}(a))

Hint: We have provided you an implementation of the Haversine distance in map_utils.py. You should be using your shortest_path implementation! The RoadNetwork class also has useful methods for extracting the latitude/longitude of a vertex in the graph.

Don’t forget to convert your estimated distance back to the real distance from source to destination.

TA Checkpoint: Test your implementation running the road_network.py file, and show the resulting graphs to your TA!

Hint: To help verify your code, you can check to see if the solution from your Dijkstra implementation agrees with the solution from your A* implementation.

python road_network.py --cost length --no-plot --source <LOCATION 1> --destination <LOCATION 2> [--heuristic]

Final TA Checkpoint: If implemented successfully, your A* heuristic should speed up searching for the shortest path between two input locations. Find a couple pairs of locations demonstrating this speedup!

If you have any feedback, you can fill out this anonymous Google Form!