The current public transportation guidance models are static and based on travel times, travel distance and travel costs. However latest survey shows that travel time has become the key factor for passenger travel route selection in big cities. Dynamic public transportation guidance model based on travel time and waiting time was proposed and the effectiveness of this model is proved in this paper. To solve this model efficiently, this paper proposed the application of A* algorithm in dealing with this models using straight line distance between two bus stops in electronic maps as Priori knowledge. Finally, the developed model and algorithm were implemented with 50 random OD pairs based on Guangzhou’s public transportation networks (containing 471 public transportation routes and 1040 stops) and Guangzhou’s electronic map. Their computational performance was analyzed experimentally. The result indicates that the models and algorithm proposed in this paper are very efficient. The average computation time of the algorithm proposed in this paper is 0.154s and the average number of nodes selected of this algorithm is 194.2.