Random graph exploration with shortest paths