One application of negative weights in a cost graph could be energy consumption for battery electric vehicles. Downhill, regenerative breaking can result in a net increase of battery charge.