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.
Algorithm to find the total resistance between 2 vertices of a graph
2
$\begingroup$
algorithms
graphing-functions
1 Answers
6
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).
-
0@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 http://www.cs.yale.edu/homes/spielman/PAPERS/icm10post.pdf – 2014-08-26