> To me, adding a constant to all edges seems like an obvious idea to try

Yeah, as you explained that is not useful because it does not preserve the shortest-path of the original graph (which is the reason we are making all edges non-negative in the first place).

That is why Johnson's algorithm adds an edge-dependent weight to each of the edges.