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

A Research on Single Source Shortest Path Based on Genetic Algorithm

作　　者：曹大有 马斌 CAO Da-You;MA-Bin(School of Maths and Computer Science,Hanjiang Normal University,Shiyan 442000,China;Shiyan Liulin Primary School,Shiyan 442000,China)

机构地区：[1]汉江师范学院数学与计算机科学学院,湖北十堰442000 [2]十堰市柳林小学,湖北十堰442000

出　　处：《汉江师范学院学报》2021年第6期1-5,共5页Journal of Hanjiang Normal University

基　　金：教育部华为协同人项目“基于ModelArts和HiLens的人工智能实践”(项目编号:202002142063)。

摘　　要：最短路径是图论中的一个经典算法问题,目的是寻找图中两结点之间的最短路径.Dijkstra算法是很有代表性的最短路径算法,在很多数据结构专业课程中都作为基本内容并详细的介绍,主要方法是从始点起,采取贪心算法向外逐层计算,直到计算到终点为止,Dijkstra算法能计算出最短路径的值和最优解,但由于贪心算法遍历计算的节点很多,存在难理解、效率低的问题.遗传算法(genetic algorithm,GA)通常用来求解最优化问题.通过利用遗传算法的框架模型建立了一个好理解、快速的最短路径问题求解过程.The shortest path is a classical algorithm problem in graph theory,which aims to find the shortest path between two nodes in a graph(composed of nodes and paths).Dijkstra Algorithm is a very representative shortest path algorithm,which is introduced in detail as the basic content in many data structure professional courses.The main feature is that it takes the starting point as the center and extends outward layer by layer until it extends to the end point.Dijkstra Algorithm can get the optimal solution of the shortest path,but it has the problems in difficult understanding and low efficiency because it traverses many nodes.Genetic Algorithm is an algorithm that simulates the biological evolution mechanism in nature,which follows the law of survival of the fittest and survival of the fittest and is usually used to solve optimization problems.In this paper,a better understood and faster shortest path-solving process is established by using the framework model of Genetic Algorithm.

关 键 词：最短路径 遗传算法 智能算法 交叉突变 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]