An Arc-labeling Shortest Time Path Algorithm
Feng Lu · Geo-information Science · 2008
Label-setting algorithm is one of the most classic shortest path algorithm,and widely used in the field of transportation.In the field of transportation,the shortest time path is more significant than the shortest length path.And the shortest time path is related with many factors such as the hierarchy of the roadway,the average speed and the delay from one roadway to another.In general,a logic road network is produced from a real one in this way: the real roadway is Abstracted as an arc in the logic network and the node is the crossing.After a brief description of some typical kinds of transportation network data model,an arc-labeling time shortest path algorithm is discussed here,which is more suitable than the node-labeling shortest path algorithm.The principle and theory analysis are presented in this article as well as the base data and running structure.In the following the characteristics and advantages of the arc-labeling algorithm,compared to node-labeling algorithm,are given.That it is more easily to calculate the delay and trace the time shortest path in arc-labeling algorithm.By the theory analysis and experiment test,it is proved that the arc-labeling algorithm can take the traffic informat affect and turning delay into account easily.So it is a practical shortest time path algorithm.