动态速度和代价约束的最短路径算法

A Shortest Paths Algorithm with Dynamic Speeds and Costs Constraint

Dijkstra算法是计算有向图中一个节点到其余各个节点最短路径的著名多项式时间算法,在交通规划、地理信息系统等方面有重要的应用。本文改进Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径,即有向图的节点之间除了静态的距离外,还有动态的速度和代价,例如城市交通中的高峰与非高峰时段影响速度/时间,收费与非收费路段影响代价;时间和代价在最短路径中由一个比例因子控制,通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的,实验结果也表明了该算法的有效性。

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.