The Dijkstra Shortest Path Optimization Algorithm Research And Implementation, In Car Navigation

The automobile navigation system is becoming one of the multi-technologies application areas with the fast development of the computer technology, navigation technology and space technology. The issue of shortest path as the core part of navigation, becomes one of the hot topics. This thesis deals with the topology of the map, reduces the number of nodes and paths, and provides an appropriate rectangle boundary according to the source and destination to decrease the searching area. Making use of directive searching, it gets the result of the distance between a node and the source plus the distance between a node and the destination. Then it chooses the minimum distance as the rule. Binary Sort Tree is adopted to generate the shortest path. It proposes an optimized Dijkstra shortest path algorithm based on rectangle boundary area and Binary Sort Tree.Furthermore, this paper proposes and realizes the automobile navigation teaching experimental system based on research platform supported by Shanghai ShuTian digital technology limited company. And the improved Dijkstra Shortest path algorithm is tested in the system. Experimental results show that the proposed algorithm provides fast searching speed. The experimental system is protected by patent right NO 200520047201.3, titled "Automobile Navigation Teaching Experimental System" by "Shanghai ShuTian digital technology limited company" dated on 2005-12-5.