Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 8 / c / Solution

No. For a path $P$ with $k$ edges, adding $C$ to every edge changes its cost toDifferent 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.

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.