文摘
We prove a general lower bound on the size of switching-and-rectifier networks over any semiring of zero characteristic, including the 6002073&_mathId=si1.gif&_user=111111111&_pii=S0304397516002073&_rdoc=1&_issn=03043975&md5=cc29e834216b5cbf95b45e12d0ffbef3" title="Click to view the MathML source">(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.