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

摘要：

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

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

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2013-10-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：17-21