I'm not sure they're actually using A*. In the following video, some cars are going directly right, although it isn't the shortest "bird-view" distance to their destination.
Though I can't find any official sources to back it up, various internet citizens seem to claim they're using a D* Lite algorithm. I find it hard to believe. Either they're using some much cruder algorithm or they've implemented D* Lite horribly.
http://www.youtube.com/watch?v=l_ufAd79bOA
Edit: actually, they seem blocked by cars from the left lane. They'd go left otherwise!