Courses βΈ± Algorithms

You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

#### Lecture Recording

#### In-class Quiz Questions

We worked through Dijkstra's algorithm as an adaptation of a natural modification of BFS.

- Suppose you have a graph with edge weights. Can you use Dijkstra's algorithm (the default version, where in the implementation edges never re-enter the heap) to determine distances between vertices?
- Yes, as long as all edge weights are positive.
- Yes, even with negative edge weights.
- No, even if all edge weights are positive.

## Reveal answer

Yes, as long as all edge weights are positive.

You can show the default version of Dijkstra fails with negative edge weights, but a proof of correctness can be obtained under the assumption of positive edge weights.

- Compute the sequence of vertices visited by a run of Dijkstra starting at vertex S on the following graph. What is the last vertex visited?

## Reveal answer

B

Follows from a direct simulation.