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

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