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.

Β