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.
- 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?
- Possibly
- Never
- Always
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.
- 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?
- Possibly
- Never
- Always
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.
- 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?
- Possibly
- Never
- Always
Reveal answer
Possibly
Answer similar to Q1.
- 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?
- Possibly
- Never
- Always
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.
Β