As a disclaimer, this is the first time I'm reading about retiming, but I do have some academic learning of optimization.
why put a negative sign to d(u) in step 1 ?
"Applying negative sign" (i.e. multiply by -1) is commonly used in optimization to swap problems between "max" and "min". As a crude example, visualize a cost function with a known minima, such as a quadratic function. If you multiply it by -1, that minima has now become a maxima, but the solution ("where is that optimal point located?") remains the same.
As per the definitions of W and D:
and the description of the algorithm says it will "compute both W and D". I can only deduce the \$-d\$ is with the intention of transforming the combined "min-max" problem into a single "min-min" problem.
Why there is no subtraction operation for W(u, v) in step 3?
Because \$w\$ are edge weights (\$W(u,v)=w(e)\$) and \$d\$ are vertex weights (\$D(u,v)=d(v)+d(u)\$). From the first step of setting up the algorithm, \$x\$ corresponds to \$w(e)\$ and \$y\$ corresponds to \$-d(u)\$. This means \$W(u,v)=x\$, but you still need to calculate \$D(u,v)\ = d(v)-y\$.