Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter

The paper studies how a programmable-matter system (modeled by the geometric amoebot model) can compute shortest paths. It focuses on a reconfigurable circuit extension where amoebots can instantly exchange simple signals through circuit connections. The authors propose two distributed algorithms for the shortest path forest problem: given k sources and ℓ destinations, the system builds a forest that links each destination to its closest source along a shortest path. For hole-free structures, one algorithm builds a shortest path tree for a single source in O(log ℓ) rounds. The second algorithm builds a shortest path forest for multiple sources in O(log n log^2 k) rounds. The first algorithm is also described as giving fast solutions for special cases like single pair shortest path (SPSP) and single source shortest path (SSSP).