= Failure of uniform edge shifts to preserve shortest paths
{title2=$w'(P)=w(P)+C|P|$}
Adding the same constant $C$ to every <edge weight> adds $C$ times the number of edges to each path's cost. Routes with different edge counts need not retain their order. For example, edges $s\to t$, $s\to u$, $u\to t$ of weights $1,-2,2$ 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.
Back to article page
