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?
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.
(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 ?