Exercise 26.5-5

Because every vertex v, |V|+1 > h[v] > k can not reach sink. Hence, we can set the height to |V|+1.

Exercise 26.5-4

We can prove the times we call the nonsaturating push, and we use the distance funcion d instead of height function h. Let K = . For a node v, let d’(v) = || / K. Set the potential function = . We divide the algorithm into phase, the phase is between consecutive change  of d* = . We can classify the phases into two category: cheap and expensive. Cheap phase contains at most K nonsaturating push. We know there are at most cheap phase, and every expensive will decrease the potential function by K. The time complexity will become .

Exercise 26.5-3

It is valid, but the relabel operation may not create admissible edge. Hence the time complexity will increase.

Exercise 26.5-2

Iit is the same as relabel to front algorithm

Exercise 26.5-1