MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

If there is a vertex at distance two which has at least 2 shortest paths to the source vertex, you have found your $C_4$. That's $O(n^3)$.
If there is a vertex at distance two which has at least 2 shortest paths to the source vertex, you have found your $C_4$. That's $O(n^3)$.