$ mkdir ~/cs170/labs/lab33 $ cd ~/cs170/labs/lab33
We had quite the stuggle on Monday dealing with the Minimum Spanning Tree algorithms. It seems like there were many people who did complete it. However, there was a core section of the class that was just completely lost. Today I'm going to re-iterate the algorithm, and then describe how I go from that algorithm to the code.
The Minimum Spanning Tree algorithm can be used to find a set of edges which contain the smallest cost that connects the entirety of the graph. However, what if we just wanted to know what the "cheapest" path is between two verticies of the graph?
The MST algorithms make no guarantee that they will represent the shortest path between two verticies in the graph. A different algorithm, created by , will find the shortest path between two specified verticies. We will cover this algorithm today in class.
It is imperative that you stop me the moment something doesn't make sense. This is the only way we can make sure that everyone understands the algorithm before we move onto coding them up.
Dijkstra's algorithm can be thought of as a very simplistic form of Dynamic programming. Instead of trying to solve the whole problem all at once, try to solve smaller problems that can then be used to build up the solution to the larger one. We accomplish this by keeping track of a cost list, and iteratively expanding the area of explored verticies using the shortest paths possible until we find the one that reaches our destination.
Create a method called dijkstra(self, start_vertex, end_vertex) in
the Graph class linked below. This method should take
two integers as parameters:
labels of the starting vertex and the ending vertex.
It should return a list of edges that are on the shortest path from
start to end.
The algorithm in question begins by defining 4 lists: a list of
visited verticies, a list of unvisited verticies, a list of costs,
and a list of predecessors. The list of visited verticies starts
with the start vertex, and all other verticies exist in the
unvisited list. Your cost list will have a cost for each vertex in
your graph, and will be infinity (float('inf')) except
for the start_vertex which will be 0. And your predecessor
list will start with a -1 value for all verticies.
Dijkstra's algorithm has a current vertex (which is originally your start_vertex), and updates the cost and predecessor lists based on the distances from the current vertex. If the cost to the current vertex (the value stored within the cost list) plus the distance to a neighbor (the value stored in the adjacency matrix) is less than the current value stored in the cost for neighbor, you update the value in cost, and set the predecessor of neighbor as current.
You continue until you reach the destination (the destination appears in visited). Then you just need to backtrack through the predecessor list starting at destination.
>>> weights = Graph("test_files/weighted.txt")
>>> print(weights.dijkstra(1, 4))
[(1, 0), (0, 4)]
>>> print(weights.dijkstra(2, 5))
[(2, 0), (0, 5)]
To simplify your code a little bit, write a method
called update_cost, which takes the source
label, the destination label, the costs list, and the
predecessor list. It should update the cost and predecessor
lists when appropriate.
You will also want to write a method
called get_path, which takes the predecessor
list, the source label and the destination label. This method
should return a list of edges that can be used to traverse
from source to destination.
This information is currently stored within the predecessor list. A non-negative value \(j\) in the predecessor list at index \(i\) means that the edge \((j, i)\) appears in the shortest path from the source to the node \(i\).
Keep in mind that this list will likely be backwards if you
just naively append edges to the list. Either reverse
the list after you compute it, or use the insert
method of lists.
This specification of Dijkstra's algorithm is \(O(V ^ 2)\). This is largely due to the fact that we have to find the vertex with the lowest current distance, which is currently done in \(O(V)\) time. A better solution would be to use a more complicated data structure to perform this action in \(O(log (V))\) time.
The better solution uses a priority queue. Whenever you update the distance to a vertex, you add it to the queue with its currently known shortest distance as its priority. Whenever you go to get the unvisited min, you simply dequeue the element from the front of the queue. A vertex might appear multiple times within the queue! Make sure you handle this case gracefully.
When you have finished, create a tar file of your
lab33 directory. To create a tar
file, execute the following commands:
cd ~/cs170/labs tar czvf lab33.tgz lab33/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
33. Make sure you include a header
listing the authors of the file.