Lower Bounds on Running time of Graph Algorithms Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.

Following is a result that I could find [see ref L92]:


3-Coloring of an n-cycle requires $\Omega(\log^*{n})$ time.


I was curious to know whether there has been any progress/work in the direction of getting
lower bounds for problems like: Shortest Paths(with/without negative weights), Mincut, 
s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related to
this are very much appreciated and helpful.

Reference

[ L92 ] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Com-
puting, 1992, 21(1), pp. 193-201

EDIT: As suggested by Robin Kothari in the comments, I am making the question more directed.
In the PRAM model without bit operations, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1]. 

Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial optimization problems. See here, here, or the original paper for more details.

[1] Mulmuley, K. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput., 28(4), 1460–1509, 1999. (from author's webpage without paywall)