Ford Fulkerson maximum flow for all vertices
"J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." provides an algorithm to compute the min cut for a fixed s on the source side with time-complexity $O(nm \log(n^2/m))$, by reducing the complexity of multiple s-t cuts for varying sinks to the complexity of a single call to the Push-Relabel max-flow algorithm. 

This might be adaptable to a version where you can store all the intermediate min-cut values (=max-flow values) for all sinks along the way.