Not as complicated as you might think. You essentially add time as an extra dimension to your graph, true, but because you're dealing with discrete vehicles instead of a continuously varying function, you can take shortcuts that make that portion of it pretty simple. It's the walk to and from the transit stops, in my experience, that's a PITA to deal with when you're trying to do transit routing.