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.
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.
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.
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.
