一种基于STL的高效最短路径算法

摘要

最短路径分析是网络拓扑中的一个重要的应用，它在地理信息系统、计算机网络路由等方面发挥着至关重要的作用。解决最短路径问题的经典方法是Dijkstra算法，时间复杂度为O(n2)，在大数据量下效率低下而且使用邻接矩阵存储图形数据在一定程度上造成了空间浪费。该文在分析了Dijkstra算法的基础上提出来一种改进方法，该法使用STL容器来代替邻接矩阵来存储图形数据提高了查询效率，并且利用双队列来存储节点降低了内循环次数，减少了很多不必要的计算，从而降低了算法时间复杂度。STL容器的应用使得最短路径算法得到了扩展，在求解最短路径的同时还支持添加障碍点，增加开关节点等应用。