= Solution
\b[No.] For a path $P$ with $k$ edges, adding $C$ to every edge changes its cost to
$$
w'(P)=w(P)+Ck.
$$
Different paths can have different numbers of edges, so this transformation need not preserve their order.
For a concrete <Directed acyclic graph>, use edges $s\to t$ of weight $1$, $s\to u$ of weight $-2$, and $u\to t$ of weight $2$. Originally the route through $u$ has cost $0$ and beats the direct edge of cost $1$. Adding $C=3$ makes every edge positive, but the direct route now costs $4$, while the route through $u$ costs $1+5=6$. <Dijkstra's algorithm> on the modified graph therefore returns a path that is not shortest in the original graph.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/functional-main-2015-edge-weight-shift.png]
{title=Adding a constant to edge weights reverses the shortest-path choice}
The two-edge path receives the added constant twice; the direct path receives it once. This is the <failure of uniform edge shifts to preserve shortest paths>.
Back to article page
