在城市道路交通网中求最短路的新算法

A New Algorithm for Finding Shortcut in a City's Road Net

在一般有向图中最短路问题是没有好算法的。任何一个城市道路交通网可以看作一个赋权有向图。本文就一般的城市交通道路网中道路间的拓扑结构和特性进行了分析,得到一种求城市道路交通网中给定两点间最短路的多项式时间近似算法,算法复杂性由交通网中结点数的多项式决定。

There is no good algorithm for finding shortcut in the directed digraph. We could regard the city's road net as a weighted directed digraph with some special qualities. In this article, we present an algorithm of which based on the analysis of the topologic structure and characteristic among roads in the road net. And the algorithm's complexity is proportion to the power of the nodes in the road net.