论文部分内容阅读
在一般有向图中最短路问题是没有好算法的。任何一个城市道路交通网可以看作一个赋权有向图。本文就一般的城市交通道路网中道路间的拓扑结构和特性进行了分析,得到一种求城市道路交通网中给定两点间最短路的多项式时间近似算法,算法复杂性由交通网中结点数的多项式决定。
There is no good algorithm for the shortest-path problem in a general directed graph. Any urban road network can be regarded as a weighted directed graph. In this paper, we analyze the topological structure and characteristics of roads in a typical urban road network, and obtain a polynomial time approximation algorithm for finding the shortest path between two given points in an urban road network. The complexity of the algorithm is determined by the nodes in the transport network The polynomial of points is decided