基于元胞自动机的单源点最短路求解算法-陕西师范大学学报期刊社网站

陕西师范大学学报（自然科学版）

数学与计算机科学

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

丁晓阳1，郭晓亭2

(1 兰州商学院信息工程学院，甘肃兰州 730020;2 陕西师范大学现代教学技术教育部重点实验室，陕西西安 710062)

丁晓阳，男，副教授，主要研究方向为管理信息系统和软件工程.E-mail:dingxy@lzcc.edu.cn.

摘要:

针对图的单源点最短路问题，提出一种改进的基于元胞自动机模型的求解算法并分析了其算法复杂度.该算法定义了一个元胞自动机模型，通过元胞空间上元胞状态的变化，能够获得某设定结点到其他结点的最短路.在实验阶段，分别用经典Dijkstra算法和提出的算法对随机生成的不完全无向图进行分析.结果表明，相比于经典的Dijkstra算法，该算法不但能够获得与之相同的仿真结果，并且具有规则简单、易于实现、效率高等特点，具有明显的优越性.

关键词：

元胞自动机；单源点最短路；并行算法

收稿日期：

2012-11-05

中图分类号：

TP301.6

文献标识码：

文章编号：

1672-4291(2013)03-0017-05

基金项目：

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

Doi:

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

DING Xiao-yang1， GUO Xiao-ting2

(1 School of Information Engineering， Lanzhou University of Finance and Economics， Lanzhou 730020， Gansu, China;2 Key Laboratory of Modern Teaching Technology， Ministry of Education， Shaanxi Normal University，Xi′an 710062， Shaanxi, China)

Abstract:

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.

KeyWords:

cellular automata; monophyletic shortest path; parallel algorithm