城市交通中结点约束的动态最短路径查询算法  

New Algorithm to Get Shortest Path in the Transportation of the City with Obligatory Nodes

作　　者：仵冀颖[1] 阮秋琦[1] 

机构地区：[1]北京交通大学信息科学研究所,北京100044

出　　处：《计算机工程与应用》2006年第28期227-229,共3页Computer Engineering and Applications

基　　金：北京市共建项目(编号:SYS100040409)

摘　　要：城市交通中道路拥堵情况多变,在车辆行进过程中两点间最短路径会发生改变。文章提出基于Dijkstra的动态更新算法,同时考虑必经结点对算法的影响,计算复杂度大大降低。文中给出了算法的理论依据,处理过程及最终效果图。The complexion of the road in the city changed with the time,the shortest path between two nodes will be changed when the vehicle is iunning.In this paper,we introduce a new dynamic algorithm based on Dijkstra,and take into account of the obligatory nodes,the calculate complication can be reduced.We specify the theory of the algorithm, the process and the graph of the effect.

关 键 词：动态更新 最短路径 必经结点 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]