基于元胞自动机的单源点最短路求解算法  

A novel method for solving monophyletic shortest path problem based on cellular automata

作　　者：丁晓阳[1] 郭晓亭[2] 

机构地区：[1]兰州商学院信息工程学院,甘肃兰州730020 [2]陕西师范大学现代教学技术教育部重点实验室,陕西西安710062

出　　处：《陕西师范大学学报（自然科学版）》2013年第3期17-21,共5页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(11172342);教育部"新世纪优秀人才支持计划"资助项目(NCET-11-0674);陕西省自然科学基金资助项目(2012JM8043)

摘　　要：针对图的单源点最短路问题,提出一种改进的基于元胞自动机模型的求解算法并分析了其算法复杂度.该算法定义了一个元胞自动机模型,通过元胞空间上元胞状态的变化,能够获得某设定结点到其他结点的最短路.在实验阶段,分别用经典Dijkstra算法和提出的算法对随机生成的不完全无向图进行分析.结果表明,相比于经典的Dijkstra算法,该算法不但能够获得与之相同的仿真结果,并且具有规则简单、易于实现、效率高等特点,具有明显的优越性.A novel method for solving monophyletic shortest path problem based on cellular automata is proposed and the complexity of this algorithm is also analyzed. The algorithm gives the shortest path from a settled node to the other nodes in the graph through changing cellular states in the cellular spaces. In the experiment, randomly generated incomplete undirected graph is analyzed by the classical Dijkstra algorithm and the proposed algorithm, respectively. Finally, the experiments show that the proposed algorithm can get the same results with the Dijkstra algorithm, and the rules are simple, easier to implement, more efficient, and have obvious superiority.

关 键 词：元胞自动机 单源点最短路 并行算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]