3 ms·
Yes, indeed. 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
by gnull 3y ago
Yes, indeed.
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.