Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
Thanks for this solution @aelguindy , I implemented it in C++ . However the Matrix required to solve this is VXV as I understand it, where V= vertices in graph. VXV is too large , V=800k . Is there a solution that has better space complexity. – Govinda Keshavdas Aug 26 '14 at 18:22
@GovindaKeshavdas what you're looking at is a Laplacian matrix. There are several ways to approximate effective resistances (or equivalently the current flow). Read this – aelguindy Aug 26 '14 at 23:49

Your Answer


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.