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`.