X-ray diffraction experiments have shown that sodium exhibits a dramatic pressure-induced drop in melting temperature, which extends from 1000 K at ~30 GPa to as low as room temperature at ~120 GPa. Despite significant theoretical effort to understand the anomalous melting, its origins are still debated. In this work, we reconstruct the sodium phase diagram by using an ab initio quality neural-network potential. Furthermore, we demonstrate that the reentrant behavior results from the screening of interionic interactions by conduction electrons, which at high pressure induces a softening in the short-range repulsion.