Edmonds-Karp One Augmentation

Problem

Run a single Edmonds-Karp augmentation step in a directed capacitated network.

Use BFS on the residual capacities to find a shortest augmenting path from s to t. Return [path, bottleneck] where path lists the nodes from s to t and bottleneck is the flow that would be pushed, or [[], 0] when no augmenting path exists. edges is a list of [u, v, capacity] triples.

Hint

BFS explores edges with positive residual capacity and records each node's parent.

Test cases

case 1

in: [4,[[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]],0,3]

expected: [[0,1,3],2]

case 2

in: [3,[[0,1,1],[1,2,1]],0,2]

expected: [[0,1,2],1]

case 3

in: [3,[[0,1,5]],0,2]

expected: [[],0]

case 4

in: [4,[[0,1,1],[0,2,1],[1,3,1],[2,3,1]],0,3]

expected: [[0,1,3],1]

Starter codePython

def edmonds_karp_one(n, edges, s, t):
    # Your code here
    pass

4 test cases · run your code against them in the editor