The weekend before the May long weekend is when the campgrounds open. That weekend should be OK to start cycling ... however, don't rule out snow. I've cycled in the Rockies on the May long weekend, and it has snowed.

Oh yes ... I should mention that the May long weekend will be busy. It's the first long weekend of the summer season and people love to camp. If you're planning to be anywhere along the Icefield Parkway on that weekend, you'll want to consider booking now.

The May Long Weekend:
http://www.timeanddate.com/holidays/canada/victoria-day