A Shortest Paths Algorithm with Dynamic Speeds and Costs Constraint
Yuan Guo-we · Journal of Guizhou University · 2015
The Dijkstra algorithm is a famous polynomial time algorithm which computes the shortest path from a source node to the others of a directed graph. It has been extensively adopted in traffic planning geography information system. An improved Dijkstra algorithm was proposed which computes the shortest path between nodes in a directed graph with dynamic speed and cost constraint. That is,it has dynamic speed and cost besides the static distance in the graph. For example,the peak or off-peak hours influences the speed / time of a road,and turnpike or non-tolling road influences the cost in urban communications. The time and cost is controlled by a scaling factor in the shortest path. By adjusting the factor it can compute shortest time / distance and minimum cost path between nodes. The improved algorithm is proved to be reliable,and the experimental results also demonstrate the effectiveness of the algorithm.