基于遗传算法的单源最短路径研究

摘要

最短路径是图论中的一个经典算法问题,目的是寻找图中两结点之间的最短路径.Dijkstra算法是很有代表性的最短路径算法,在很多数据结构专业课程中都作为基本内容并详细的介绍,主要方法是从始点起,采取贪心算法向外逐层计算,直到计算到终点为止,Dijkstra算法能计算出最短路径的值和最优解,但由于贪心算法遍历计算的节点很多,存在难理解、效率低的问题.遗传算法(genetic algorithm,GA)通常用来求解最优化问题.通过利用遗传算法的框架模型建立了一个好理解、快速的最短路径问题求解过程.