If the graph is not strongly connected, the modification will not work.
If the graph is strongly connected, then for every vertex v, h(v) is well-defined and the nonnegative property is preserved.
July 1, 2007
Exercises 25.3-5
According to (25.9), we know w’(u,v) = w(u, v) + h(u) – h(v), h(u) is the shortest path from s to u. If (u,v) is a edge in the cycle, then the shortest path from v to u is -w(u,v). Suppose that w(u,v) is positive, h(v) will be 0 and h(u) will be -w(u,v), so w(u,v) + h(u) – h(v) = 0. The case of w(u,v) is negative is symmertic.
Exercises 25.3-4
It will change the shortest path. The path with more edges will be added more weight.
Exercises 25.3-3
Because w(u,v) ≥ 0 for all edges, the shortest from s to every vertex v must be edge (s,v) which weight is 0. Hence the codomain of function h has only one element — 0 and w and w’ must be identical.
