Shortest path length with bounded-alternation \((\min ,+)\) formulas

We study bounded-depth \((\min ,+)\) formulas computing the shortest path polynomial. For depth 2d with \(d \ge 2\), we obtain lower bounds parameterized by certain fan-in restrictions on \(+\) gates except those at the bottom level. For depth 4, in two regimes of the parameter, the bounds are tight.