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

Recall the main topic.

- Consider the following example: there are four nodesย ๐,๐,๐,๐ย (nodeย ๐ย is the source), and four arcs:ย ๐โ๐ย with cost 10,ย ๐โ๐ย with cost 4,ย ๐โ๐ย with cost -8, andย ๐โ๐ย with cost 1.ย What will Dijkstra report as the length of the shortest path from ๐ to ๐?

## Reveal answer

5

Answer by direct simulation.

- Does Dijkstra work in the presence of negative edge weights?
- Yes
- No

```
Dijkstra(s):
InitSSSP(s)
For all vertices v:
INSERT(v, dist(v))
while the priority queue is not empty:
u = extractmin()
for all edges (u,v):
if (u,v) is tense:
relax(u,v);
decreasekey(v,dist(v))
```

## Reveal answer

No

Please see the lecture for a discussion on this. How did we modify this to make it work?

ย