Dinic Level Graph Depth

Problem

Compute the BFS level of the sink in Dinic's residual level graph.

Build the residual capacity matrix from the directed edges, run a BFS from s that only follows positive residual capacity, and return level[t]; the level counts the number of residual edges on the shortest augmenting path. edges is a list of [u, v, capacity] triples. Return -1 when t is unreachable.

Hint

The BFS levels form the layered graph that Dinic's blocking flow must respect.

Test cases

case 1

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

expected: 2

case 2

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

expected: -1

case 3

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

expected: 3

case 4

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

expected: -1

case 5

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

expected: 1

Starter codePython

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

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