I came upon this implementation of the dfs in Dinic’s algorithm written in Python
def dfs(c, f, current, capacity): tmp = capacity # What's the purpose of that? # we want to get to the sink, but we want it to be a blocking flow path if current == NROW - 1: return capacity for i in range(NROW): is_next = levels[i] == levels[current] + 1 residual_capacity = c[current][i] - f[current][i] has_more_capacity = residual_capacity > 0 if is_next and has_more_capacity: min_capacity_so_far = min(tmp, residual_capacity) flow = dfs(c, f, i, min_capacity_so_far) f[current][i] += flow f[i][current] -= flow tmp -= flow # Why do we do that return capacity - tmp # Why do we return capacity - tmp
How do we know that this dfs finds a blocking path? Also, I can’t seem to understand the usage of the temp variable.
Thanks in advance!