Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume we have a graph, and resistors are placed on the edges. I want to know if there is an algorithm that find the total resistance between any 2 vertex. i have a hard time finding any description of such algorithm.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

I am very very rusty on this topic.

I remember that the node voltage method (which is just a shortcut over Kirchhoff's laws) involved only equations written on the nodes (no cycle equations). Therefore, you can easily generate the system of equations in linear time and then solve it (by Gaussian elimination) in cubic time in the number of nodes.

EDIT: Actually, I was feeling a bit bored, so here is a simple implementation (naive though).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.