6 Sep, 2021

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

✅

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))

Reveal answer

✅

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