Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Question 2.1

In the shortest path problem we are given a directed graph G and a starting and ending vertex. The goal is to find the shortest path from the start to end vertex. Here, we keep track of the total path length. A different starting vertex will change the whole tree.

In the minimum spanning tree problem we are given an undirected, weighted graph. The goal here is to find the minimum-weight set of edges such that we can get from any vertex in the graph to any other utilizing that set of edges. Here, there is no specific start node because the goal is to minimize the edge weights sum. Most of the time, there is only one possible MST which has the minimum sum. We keep track of the cheapest edges that maintain connectivity.

Question 2.2

Dijkstra's algorithm picks an unknown vertex with smallest cost where cost = distance to the source. On the other hand, Prim's picks an unknown vertex with smallest cost where cost = distance from this vertex to the known set. In other words, the cost of the smallest edge connecting this vertex to the known set. Besides this, the two are practically identical.

Question 3

Question 3.1-3.8

Below is an explanation of this algorithm being run:

1. Start by initializing a table where all nodes have cost = infinity. Set the start vertex (A) to have cost(A)=0 and prev(A)=/
2. Prim's Iteration 1: Mark A as known and potentially update all its neighbors
   • Because the distance to B through A (dist(A, B) = 2) is less than the current cost(B) = infinity, update cost(B) = 2 and prev(B) = A.
   • Because the distance to C through A (dist(A, C) = 2) is less than the current cost(C) = infinity, update cost(C) = 2 and prev(C) = A.
   • Because the distance to D through A (dist(A, D) = 1) is less than the current cost(D) = infinity, update cost(D) = 1 and prev(D) = A.
3. Prim's Iteration 2: Mark D as known and potentially update all its neighbors
   • Because the distance to E through D (dist(D, E) = 1) is less than the current cost(E) = infinity, update cost(E) = 1 and prev(E) = D.
   • Because the distance to G through D (dist(D, G) = 5) is less than the current cost(G) = infinity, update cost(G) = 5 and prev(G) = D.
   • Because the distance to F through D (dist(D, F) = 6) is less than the current cost(F) = infinity, update cost(F) = 6 and prev(F) = D.
   • Because the distance to C through D (dist(D, C) = 1) is less than the current cost(C) = 2, update cost(C) = 1 and prev(C) = D.
4. Prim's Iteration 3: Mark C as known and potentially update all its neighbors
   • Because the distance to F through C (dist(C, F) = 6) is less than the current cost(F) = 6, update cost(F) = 2 and prev(F) = C.
5. Prim's Iteration 4: Mark E as known and potentially update all its neighbors
   • Because the distance to B through E (dist(E, B) = 2) is less than the current cost(B) = 2, update cost(B) = 1 and prev(B) = E.
   • Because the distance to G through E (dist(E, G) = 3) is less than the current cost(G) = 5, update cost(G) = 3 and prev(G) = E.
6. Prim's Iteration 5: Mark B as known and potentially update all its neighbors
   • No unknown neighbors
7. Prim's Iteration 6: Mark F as known and potentially update all its neighbors
   • Only undiscovered neighbor is G which has a greater edge cost than its current, so no updating
8. Prim's Iteration 7: Mark G as known
   • Last node!