# Practice Exercises, lecture on Dijkstra's algorithm¶

### Exercise 1¶

Give an example of a graph with negative edge weights for which Dijkstra's algorithm would fail. Why does the invariant from the slides fail in this case?

### Exercise 2¶

Suppose we define a different kind of graph where we have weights on the vertices and not the edges. Does the shortest-paths problem make sense for this kind of graph? If so, give a precise and formal description of the problem, and show how to transform the input to solve the problem via a standard shortest-paths algorithm. If not, explain why not.

### Exercise 3¶

(a) Suppose we want to find the shortest distance from $s$ to some particular vertex (rather than to all vertices reachable from $s$). What would we do?

(b) What if we want to find the shortest path between every pair of vertices in the graph ?