On the optimality of Bellman–Ford–Moore shortest path algorithm

We prove a general lower bound on the size of switching-and-rectifier networks over any semiring of zero characteristic, including the (min⁡,+)(min⁡,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum operations are allowed.