You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.
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 𝑑?
Answer by direct simulation.
- Does Dijkstra work in the presence of negative edge weights?
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))
Please see the lecture for a discussion on this. How did we modify this to make it work?