2025-275

The following image illustrates the Push-Relabel algorithm partially executed on a flow graph, with the respective residual graph displayed on the right. The algorithm repeatedly performs relabel and push operations on a node, trying to push as much flow as possible to neighbors in alphabetical order. A FIFO queue of active nodes (the ones that have excess flow) is used to select the next node to act upon, initialized with the source only.  If a node cannot push all its excess flow, it returns to the FIFO queue.

Based on the process illustrated, mark the correct alternative of the next step in the algorithm:

a) Relabeling of 'a', setting 'h' to 8, and returning the excess flow to 'S' using Push.

b) Relabeling of 'c', setting 'h' to 2, and returning the excess flow to 'b' using Push.

c) Relabeling of 'c', setting 'h' to 8, and returning the excess flow to 'S' using Push.

d) Relabeling of 'e', setting 'h' to 1, and pushing the excess flow to 't'.

e) None of the above 

 

 Original idea  by: Giorgio Rossa