Post
by **Destination Goa** » Fri Feb 18, 2005 1:50 pm

What is m? Number of resistors? If so, then m = O(n^2).

About auto-elimination. Do you mean eliminating resistors connecting same pair nodes or something else? I think we talk about different solutions here.

Mine is: let x[1]...x[N] be potentials of N nodes. c[1]...c[N] is current excess (0 for all, except +1 for source and -1 for destination). Equation system is X*A=C.

Initially A is all zeroes. Then, for each resistor R connecting V1;V2

a[v1][v2] += 1/r;

a[v1][v1] -= 1/r;

a[v2][v1] += 1/r;

a[v2][v2] -= 1/r;

So, this is O(m+n^3) solution (n - number of nodes, m - number of resistors), and it sums duplicate resistors automatically. Actually, it stores sum(1/R1+1/R2+...+1/Rk) for each pair (v1;v2) where resistors R1...Rk connect this pair in either direction.

To be the best you must become the best!