Research And Implementation Of The Optimal Path Algorithm Based On Geographic Information Systems

The shortest path problem is very important in the network optimizing. In Study of the sta(?)network optimizing, it is assume that the weight of the arc in the network is static, in the common circumstances, the algorithm of static network can deal the problem well. But in some circumstances like there are confined area, high demond to the time and performance or both, the assume of static network is not suitable. Add the time variable to the network model, the study of algorithm of time-dependent network, break the limit of static network, so the model is more flexible and veracious. This problem is already the hot spot in the area of network optimizing.This thesis introduces some basic concepts of Geographical Information System(GIS) including the data model of GIS, the data organizing and manage of GIS, and the analyzing of network of GIS. At the base of study and summarizing to the static shortest path algorithm, the thesis implements a shortest path algorithm in the vector map, including reading the binary file of map, building of road network, query of road attributes, drawing of enemy information, and realizing of shortest path and so on.Combining some literature this thesis also does some study to the shortest path problem of time-dependent network. At the base of real state of traffic network, from the statistic characteristic of the traffic stream, the thesis dose some study on how to improve algorithm of time-dependent network, at the base of dynamic information, using a dynamic method to compute the time of getting through a path, which can depict the topology of network more exactly. By way of setting suitable rule of searching to reduce the scale of algorithm searching, minimize the complexity, improve the efficiency of a system.