在城市道路交通网中求最短路的新算法
贺红1
马英红2
马绍汉1
1.山东大学,计算机科学与技术学院,山东,济南,2501002.山东大学,数学与系统科学学院,山东,济南,250100
摘要：在一般有向图中最短路问题是没有好算法的.任何一个城市道路交通网可以看作一个赋权有向图.本文就一般的城市交通道路网中道路间的拓扑结构和特性进行了分析,得到一种求城市道路交通网中给定两点间最短路的多项式时间近似算法,算法复杂性由交通网中结点数的多项式决定.
关键词：城市交通网最短路赋权有向图好算法
分类号：U491.1(交通工程与公路运输技术管理)
论文发表日期：2002-01-01
在线出版日期：2026-05-22（本平台首次上网日期，不代表文献的发表时间）
页数：3( 66-68 )
英文信息