Failure of uniform edge shifts to preserve shortest paths
ID: failure-of-uniform-edge-shifts-to-preserve-shortest-paths
Adding the same constant to every edge weight adds times the number of edges to each path's cost. Routes with different edge counts need not retain their order. For example, edges , , of weights make the two-edge path optimal with cost zero. Adding three changes the direct cost to four and the two-edge cost to six. The graph is a Directed acyclic graph and all shifted weights are positive, yet the minimizing path changes.
New to topics? Read the docs here!