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

Q2.1

The purpose of Dijkstra's is to find the shortest path between nodes in a graph.

Q2.2

BFS iterates in level-order, ordering in-between levels is not important by default. So BFS uses a Queue as it's internal data structure to keep track of the ordering.

Dijkstra's iterates in priority order, prioritizing processing nodes with the next smallest estimated distance (so that we get that guarantee that we're looking at correct information). So Dijkstra's uses a PriorityQueue as it's internal data structure to keep track of the ordering.

Overall they're very similar and Dijkstra's just has a few more steps than BFS.

Question 3

Q3.1-3.6

Here is the final table of Dijkstra's after running it on this graph. This can answer questions 3.1-3.6.

Below is an explanation of this algorithm being run.

1. Start by initializing a table where all nodes have distTo=infinity . Set the start vertex (A) to have distTo(A)=0 and edgeTo(A)=/
2. Dijkstra's Iteration 1: Mark A as known and potentially update all of its neighbors:
   • Because the distance to C through A (distTo(A) + edgeWeight(A, C) = 0 + 1 = 1) is less than the current distTo(C) = infinity, update distTo(C) = 1 and edgeTo(C) = A.
   • Because the distance to B through A (distTo(A) + edgeWeight(A, B) = 0 + 4 = 4) is less than the current distTo(B) = infinity, update distTo(B) = 4 and edgeTo(B) = A.
3. Dijkstra's Iteration 2: Mark C as a known vertex, since it is the unknown node with the smallest distTo. Potentially update its neighbors:
   • Because the distance to B through C (distTo(C) + edgeWeight(C, B) = 1 + 7 = 8) is greater than the current distTo(B), we don't update anything.
   • Because the distance to D through C (distTo(C) + edgeWeight(C, D) = 1 + 2 = 3) is less than the current distTo(D) = infinity, update distTo(D) = 3 and edgeTo(D) = C.
4. Dijkstra's Iteration 3: Mark D as a known vertex, since it is the unknown node with the smallest distTo. Potentially update its neighbors:
   • Because the distance to B through D (distTo(D) + edgeWeight(D, B) = 3 + 5 = 8) is greater than the current distTo(B), we don't update anything.
   • Because the distance to E through D (distTo(D) + edgeWeight(D, E) = 3 + 7 = 10) is less than the current distTo(E) = infinity, update distTo(E) = 10 and edgeTo(E) = D.
5. Dijkstra's Iteration 4: Mark B as a known vertex, since it is the unknown node with the smallest distTo. Potentially update its neighbors:
   • Because the distance to E through B (distTo(B) + edgeWeight(B, E) = 4 + 1 = 5) is less than the current distTo(E) = 10 , update distTo(E) = 5 and edgeTo(E) = B.