摘要
结点有约束的网络是一类特殊的网络,如具有禁止通行限制信息的交通路网等,由于最短路径的求解是有后效性的,经典的Dijkstra算法等不能直接用来求解该问题,本文提出了一种结点有约束的交通网络最短路径建模方法,该方法所建模型为一般网络模型,可用任一传统高效的算法求其最短路径,从根本上降低了问题的复杂性,为很好地解决交通、通信等领域中的此类问题提供了有益的方法。
A network with node limits is a kind of special networks, such as the traffic one with ban of passing. Because the shortest path problem for this kind of network is of aftereffect, the traditional algorithms can＇t be used to find the shortest path, such as Dijkstra algorithm. The method of modeling for the shortest path problem in traffic network with node limits is discussed in this paper. By this method, the network model with limits is transformed into a common network model. Thus, the problem can be solved in any traditional algorithms. The complexity of the problem is essentially reduced. The paper provides a good way for solving this kind of problems in the fields of traffic, communication, and so on.
出处
《运筹与管理》
CSCD
2005年第4期40-43,共4页
Operations Research and Management Science
基金
国家自然科学基金资助项目(70071028)
兰州交通大学青蓝工程资助。
关键词
运筹学
交通网络
最短路径
网络模型
算法
operational research
traffic network
shortest path
network model
algorithm
