-
最短路径问题的研究起源于20世纪50年代末的一些数学游戏，是图论中的一个经典问题。它的应用来十分广泛，国内外许多学者对其进行了广泛研究，获得了许多研究成果[4-13]。直到1959年，荷兰计算机科学家Edsger Wyde Dijkstra才给出了这一问题求解的思想，并给出了具体算法，也就是众所周知的Dijkstra算法，主要解决从一个固定点到其他固定点的最短路径问题。后来通过人们的不断思考和探索，提出了海斯算法，鉴于这两种算法在含有赋权的图方面的应用局限性，因此弗罗伊德又提出了Floyd算法，有效解决含有赋权的最短路径的问题。目前，人们在实际生活中很少遇见包含负权的最短路径，因此通常情况下会选择Dijkstra算法。虽然专家们又先后提出了 算法，蚁群算法，SPFA算法等，但在所有的算法中，Dijkstra算法依然是核心，是算法中的经典。6885
- 上一篇：国内外风力发电的发展现状
- 下一篇：GPS/SINS组合定位技术国内外研究现状
经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现，这些算法在时间复杂度、空间复杂度和易实现性等方面各具特色。目前研究的热点主要集中在以下几个方面，一是针对实际应用中网络特征优化运行的结构，二是针对网络特征进行显示集合层次递归搜索，三是采用有损算法，四是采用拓扑层次编码路径视图，对最短路径进行部分实例化编码存储，五是采用并行算法为并行计算服务[1]。据统计，目前提出此类最短路径的算法大约有17种，运用最广泛的是Dijkstra算法，Floyd算法和 算法