|
|||||
|
|
| 基于元胞自动机的单源点最短路求解算法 | |
| 引用本文： | 丁晓阳,郭晓亭.基于元胞自动机的单源点最短路求解算法[J].陕西师范大学学报,2013(3):17-21. |
| 作者姓名： | 丁晓阳 郭晓亭 |
| 作者单位： | 兰州商学院信息工程学院;陕西师范大学现代教学技术教育部重点实验室 |
| 基金项目： | 国家自然科学基金资助项目(11172342);教育部“新世纪优秀人才支持计划”资助项目(NCET-11-0674);陕西省自然科学基金资助项目(2012JM8043) |
| 摘 要： | 针对图的单源点最短路问题,提出一种改进的基于元胞自动机模型的求解算法并分析了其算法复杂度.该算法定义了一个元胞自动机模型,通过元胞空间上元胞状态的变化,能够获得某设定结点到其他结点的最短路.在实验阶段,分别用经典Dijkstra算法和提出的算法对随机生成的不完全无向图进行分析.结果表明,相比于经典的Dijkstra算法,该算法不但能够获得与之相同的仿真结果,并且具有规则简单、易于实现、效率高等特点,具有明显的优越性. |
| 关 键 词： | 元胞自动机 单源点最短路 并行算法 |
| 本文献已被 CNKI 等数据库收录！ | |