46.考虑转向延误最短路径算法及实现

摘要

最短路径算法是交通分配的基础。交通网络交叉口存在转向延误和禁止转向现象,更合理的最短路径算法应该能考虑转向延误。结合交通网络的特点,对传统的邻接链表进行了改进,得到了一种新的网络存储结构,可以很方便的存储节点转向信息。以此改进的邻接链表结构为基础,设计了基于标号修正法的新最短路径算法。算法除了给节点的每个转向都设定一个标号外,还增加一个标号表示从起点出发终至于该节点的路径。用C++编程实现了该算法,在一系列不同规模的大型随机网络上,对程序进行了测试,验证了算法的可行性和高效性。