Improved calculation method of shortest path with cellular automata model

Abstract

Purpose

Shortest path problem has always been a hot topic in the study of graph theory, because of its wide application field, extending from operational research to the disciplines of geography, automatic control, computer science and traffic. According to its concrete application, scholars in the relevant field have presented many algorithms, but most of them are solely improvements based on Dijkstra algorithm. The purpose of this paper is to enrich the kinds of (and improve the efficiency of) the shortest path algorithms.

Design/methodology/approach

This paper puts forward an improved calculation method of shortest path using cellular automata model, which is designed to search the shortest path from one node to another node. Cellular state set is adjusted with combination of breeding and mature states. Evolution rule is improved to enhance its parallelism. At the same time, recording manner of cellular state turnover is modified to record all information sources.

Findings

The result indicates that the improved algorithm is correct and more efficient, in that it could reduce the times of cellular state turnover; meanwhile, it can solve multi‐paths problem.

Originality/value

In this paper, cellular state set in exiting shortest path algorithm based on cellular automata theory is adjusted; evolution rule is improved; and recording manner of cellular state turnover is modified to record all information sources. All of which make the parallelism of this algorithm enhanced and the multi‐paths problem solved.

Citation

Wang, M., Qian, Y. and Guang, X. (2012), "Improved calculation method of shortest path with cellular automata model", Kybernetes, Vol. 41 No. 3/4, pp. 508-517. https://doi.org/10.1108/03684921211229578