Weighted Directed Graph $G$ is given. there is no negative cycle. vertexes number is $1$ to $n$. weight of edge $a$ to $b$ is $P(a,b)$. $G'$ is graph $G$ with edges will be changed according to following formula. the shortest path (not about weights of shortest path, just shortest path) does not changed !!
A) $P'(a,b)=P(a,b)+a-b$
B) $P'(a,b)=P(a,b)+b-a$
here $a$ and $b$ in sum means number (i.e: $a,b$ are the numbers assigned to those two vertices.)
how we can get the point about this strange claims ?
Best Answer
Pick any path $C$ between two nodes $s$ and $t$ in $G$ and let $w$ be its total weight. After applying the rule:$$P'(a,b) = P(a,b)\ \pm(a-b)$$ the new weight is: \begin{align*} w'(s,t) &= \sum_{(u,v)\ \in\ C} P'(u,v)\\ &= \sum_{(u,v)\ \in\ C} [P(u,v) \pm (u - v)]\\ &= \sum_{(u,v)\ \in\ C} P(u,v)\ \pm \sum_{(u,v)\ \in\ C}(u - v)\\ &= w(s,t) \pm [(s - u_1) + (u_1 - u_2) + \cdots + (u_{n-1} - u_n) + (u_n - t)]\\ w'(s,t) &= w(s,t) \pm (s - t) \end{align*} This tells us that all s-t paths in $G$ are changed by an equal amount of $s-t$ and therefore their ordering is preserved.
EDIT: As per request, I will add an example. Assume the are 3 s-t paths in $G$ ordered like: \begin{align*} &w_1(s,t) &\le &\ w_2(s,t) &\le &\ w_3(s,t) &\implies\\ &w_1(s,t) \pm(s-t) &\le &\ w_2(s,t) \pm(s-t) &\le &\ w_3(s,t) \pm(s-t) &\implies \\ &w'_1(s,t) &\le &\ w'_2(s,t) &\le &\ w'_3(s,t) \end{align*} And we see that the order remains the same.