Abstract: The problem of”the shortest path" has wide application. There are many algorithms to solve this problem and the best one is "Dijkstras label algorithm".But experiment results show that this algorithm needs to be improved:① The algorithm's exit mechanism is ineffective to non-unicorn figure and will fall into an infinite loop;② The algorithm is not concerned in the problem of previous adjacent vertices in shortest path;③ The algorithm is not concerned in the problem that more vertices obtain the "xrlabcl" at the same time. hhis paper improved the "Dijkstras label algorithm".Experiment results indicate that the improved algorithm can solve above problems effectively. On the basis of the above work,we developed the "Beijing Road optimal route selection system" , which help users to select the shorted route, so that people can avoid the most congested road traffic and save time.

Key words: Shortest path, Dijkstra's labeled algorithm, Urban transport, Optimal route selection