JCA Home • Issue Contents

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 (n2) cells, is used. The algorithm runs in (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 (n log n) time.

Full Text (IP)