Find shortest paths in complement graph
I personally, do not see why this is left as unanswered.

Finding something in complement graph and finding that same thing in the graph is essentially have the same time complexity (up to constant factor).

Since swapping between edge $(u,v)$ and non-edge $(u,v)$ is just $O(1)$-time operation. We do not have to transform or convert anything just negate every query output.