Electrical Flow One Step

Problem

Compute the current on every edge when one unit of current is injected at s and extracted at t in a graph with unit resistors.

Solve the grounded Laplacian system to get node potentials, then return the current phi[u] - phi[v] for each edge in input order. edges is a list of [u, v] pairs.

Hint

Current flows downhill in potential and is conserved at every internal node.

Test cases

case 1

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

expected: [1,1]

case 2

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

expected: [0.5,0.5,-0.5,-0.5]

case 3

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

expected: [-1,1,0]

Starter codePython

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

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