# 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.

#### 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
β
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.
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 multiplied by two, will the shortest path between and change?
1. Possibly
2. Never
3. Always
β
Never
Relative costs between paths remains the same when all edge weights are uniformly scaled, as can be checked by a simple calculation.
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 decreased by one, will the shortest path between and change?
1. Possibly
2. Never
3. Always