Computing Shortest Paths with Cellular Automata
Selim G. Akl
We describe cellular-automaton-based algorithms for solving two shortest path problems on arbitrary connected, directed, and weighted graphs with n vertices. The first problem is that of finding the shortest path from a given vertex to another given vertex of the graph. A two-dimensional cellular automaton, shaped as a triangle, with O (n2) cells, is used. The algorithm runs in O (n) time. The second problem requires that all shortest paths between pairs of vertices be obtained. An n × n cellular automaton solves the problem in O (n log n) time.