1 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

πŸ“

We were working through shortest paths here and exploring how the SP structure changes if the weights change.

  1. Suppose you have a simple, undirected, edge-weighted graph and you have computed the shortest path between a pair of vertices and . If all edge weights are increased by one, will the shortest path between and change?
    1. Possibly
    2. Never
    3. Always
    4. Reveal answer
      βœ…

      Possibly

      Consider the graph where we have a direct edge from to whose weight is 4.5 and edges and with weights 2 each. Initially, the path is cheaper, but if all edge weights are increased by one, then this path has cost 6 while the direct edge is cheaper at 5.5.

  2. Suppose you have a simple, undirected, edge-weighted graph and you have computed the shortest path between a pair of vertices and . If all edge weights are multiplied by two, will the shortest path between and change?
    1. Possibly
    2. Never
    3. Always
    4. Reveal answer
      βœ…

      Never

      Relative costs between paths remains the same when all edge weights are uniformly scaled, as can be checked by a simple calculation.

  3. Suppose you have a simple, undirected, edge-weighted graph and you have computed the shortest path between a pair of vertices and . If all edge weights are decreased by one, will the shortest path between and change?
    1. Possibly
    2. Never
    3. Always
    4. Reveal answer
      βœ…

      Possibly

      Answer similar to Q1.

  4. Suppose you have a simple, undirected, edge-weighted graph and you have computed the shortest path between a pair of vertices and . If all edge weights are halved, will the shortest path between and change?
    1. Possibly
    2. Never
    3. Always
    4. Reveal answer
      βœ…

      Never

      Relative costs between paths remains the same when all edge weights are uniformly scaled, as can be checked by a simple calculation.