Commute Time

Problem

Compute the commute time C(u, v) = 2m * R(u, v) of the simple random walk on a connected undirected graph, where m is the number of edges and R is the effective resistance.

Solve the grounded Laplacian system L x = e_u - e_v with node 0 pinned to 0 using Gaussian elimination, then set R = x[u] - x[v]. edges is a list of [u, v] pairs. Return a float.

Hint

Effective resistance treats the graph as a resistor network with unit resistors.

Test cases

case 1

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

expected: 2

case 2

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

expected: 8

case 3

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

expected: 6

case 4

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

expected: 8

case 5

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

expected: 12

Starter codePython

def commute_time(n, edges, u, v):
    # Your code here
    pass

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