Courses βΈ± Algorithms

Food for thought: can you come up with an algorithm to find

*simple paths**with the lowest total cost*even if some edge weights are negative? Hint: What if you took a simple, undirected, unweighted graph, and assigned every edge a weight of ? What would a simple shortest path in such a graph correspond to? Can you relate this to some other (possibly hard) problem that you have seen before?#### Lecture Recording

#### In-class Quiz Questions

We wrapped up the discussion on DSU (the last implementation involving direct leader information in an array + a linked list threading all elements of a set) and we spent some time introducing shortest paths.

- Suppose you have a graph with edge weights. Can you use breadth-first search to determine distances between vertices?
- Yes, as long as all edge weights are positive.
- Yes, even with negative edge weights.
- No, even if all edge weights are positive.
- w((a,b)) = 3
- w((a,c)) = 1
- w((c,b)) = 1

## Reveal answer

No - BFS cannot accurately determine distances even if all edge weights are positive.

Consider the graph on vertices a, b, c, with edges (a,b), (b,c) and (a,c); with the following edge weights:

Then the distance between a and b is 2, given by the path a - c - b; but a BFS starting from a will pull both b and c in the first layer and think of the direct edge between a to b as being the shortest path; even though it's cost is 3, and 3 > 2.

## Definitions (from slides)

Β