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

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

针对图的单源点最短路问题,提出一种改进的基于元胞自动机模型的求解算法并分析了其算法复杂度.该算法定义了一个元胞自动机模型,通过元胞空间上元胞状态的变化,能够获得某设定结点到其他结点的最短路.在实验阶段,分别用经典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.