摘 要：Dijkstra算法是求解无向赋权图内单源最短路径的经典算法，然而，随着研究的深入进行，学者发现，针对串行计算机的最短路径算法，已经几乎到达理论上的时间复杂度极限。本文在一种基于图分割的Dijkstra加速算法的基础上，将每个分割成的区域由一个RMA(Region Manage Agent)进行管理，并尝试利用多个RMA协同求解最短路径问题，使该方法能够及时响应路网的变化。
关键词：最短路径；Agent；Dijkstra algorithm；运输问题
0、引言
Dijkstra算法是求解无向赋权图内单源最短路径的经典算法，它可以看作是采用了初级启发式搜索策略的广度优先搜索方法，Dijkstra可以求得类似问题的最优解。由于Dijkstra算法在实践过程中表现出了较好的网络普适性和求解问题的一般性，使其成为求解最短路径问题中应用最为广泛的一种方法。然而，随着研究的深入进行，学者发现，针对串行计算机的最短路径算法，已经几乎到达理论上的时间复杂度极限[1]。
最短路径算法在各领域的实用价值吸引了大量学者投入到这方面的研究，但大部分的研究都集中在静态网络中最短路径的优化求解，对路网状态动态变化情况下的求解方法研究较少[2]。