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.

  1. 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 ๐‘‘?
  2. Reveal answer
    โœ…

    5

    Answer by direct simulation.

  3. Does Dijkstra work in the presence of negative edge weights?
    1. 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))
      
    2. Yes
    3. No
    4. Reveal answer
      โœ…

      No

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