I cooked up this while correcting some assignments:
You are given a digraph (as adjacency lists), a source node and a target node. Find the smallest subgraph that contains all the shortest paths from the source to the target.
And here's another one:
You are given a digraph and a partition of its nodes. Test if the partition has the following property: if x->y then for all x' in the same class as x there is a y' in the same class as y such that x'->y'.