I think you can prove that one can't just map the edge weights (so that edge's new weight only depends on its original weight) to make all weights positive, and also preserve all shortest paths.
You may try something more complex, i.e. where the new weight of an edge would depend on some more edges around it. But then the cost of doing so may be close to Bellman-Ford algorithm itself.
I think you can prove that one can't just map the edge weights (so that edge's new weight only depends on its original weight) to make all weights positive, and also preserve all shortest paths.
You may try something more complex, i.e. where the new weight of an edge would depend on some more edges around it. But then the cost of doing so may be close to Bellman-Ford algorithm itself.