<p><strong>Just an extended comment to include the picture</strong>: if the following (random) resistor network is valid then the max current flow 33.9mA is not on the shortest path from $s$ (+5V) to $t$ (GND).</p>

<p><img src="https://i.sstatic.net/OE4Ks.jpg" alt="enter image description here"></p>

CC BY-SA 3.0
2012-07-26T22:51:16.353Z
I updated my question, and apologize for not explaining my conjecture clearly if that caused some confusion.
Federico Magallanez
CC BY-SA 3.0
2012-07-25T19:54:37.107Z
2012-07-25T19:54:37.107Z
Marzio De Biasi
<p>Your intuition is in a certain sense correct. By straightforward linear
algebra we can find the electric potential of each node in the
graph, given the net current from source to sink.</p>

<p>Now we can calculate the probability distribution of the path taken
by the electric current through the graph. By the second law of thermodynamics,
(that no process may independently cause a decrease in entropy,) it
is impossible for electric current to independently flow from a lower
to a higher potential, and even by the first law (conservation of
energy,) it is impossible for current to flow between nodes of equal
potential through a non-zero resistance. So every edge in the graph
is directed from a higher to a lower potential, any edges of zero resistance are identified to a single node, and any non-zero-resistance edges between
nodes of equal potential are eliminated. Thus the graph is <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noreferrer">directed
and acyclic</a>, and the path taken by the electric current from the source
node to the sink node is a finite <a href="http://en.wikipedia.org/wiki/Markov_chain" rel="noreferrer">Markov chain</a>,
because we are confident that an electric current will take an independent
and memoryless path through the given graph.</p>

<p>The Markov transition probability of each edge in the graph is then
given by the ratio of the current through that edge to the total (gross, not net!) current flowing out from the same node:</p>

<p>$$P(T_{ij})=
\frac{(I_{ij})_+}{\sum_k (I_{ik})_+}=
\frac{\frac 1 {R_{ij}}(E_{i}-E_{j})_{+}}{\sum_{k}\frac 1 {R_{ik}}(E_{i}-E_{k})_{+}}$$</p>

<p>where we have denoted the <a href="http://en.wikipedia.org/wiki/Positive_and_negative_parts" rel="noreferrer">positive part</a> of a parenthesized expression
by a subscript "+". If we compute the <a href="http://en.wikipedia.org/wiki/Self-information" rel="noreferrer">self-information</a> of each
edge</p>

<p>$$S(T_{ij})=-\log P(T_{ij})$$</p>

<p>then the shortest path weighted additively by self-information is indeed the
most likely path taken by the electric current, and <strong>the current that
actually traverses that entire path</strong> is equal to the total current times the product of the Markov transition probabilities of all the edges along that path.</p>

<p>However, as to your question the shortest path weighted by Markov self-information is not necessarily the shortest path weighted by resistance, (because of the effects of "crowding out" by current taking other paths sharing the same edge.)</p>

CC BY-SA 3.0
2012-07-27T19:09:14.337Z
I know that there's a close relation between current flow and markov chain probability which is pointed out in the book by Snell and Doyle. But I'm not sure what you mean by 'crowding out'. Can you give a reference which explains crowding out?
Federico Magallanez
CC BY-SA 3.0
2012-07-27T21:23:29.793Z
It's just my way of trying to explain that the current actually traversing a complete path under a Markov chain analysis may well be less than the minimum of the total currents for each edge on the path.  The term "crowding out" as I have used it is very non-technical, not a specific term that can be referenced in the literature.  Sorry if that confused you.
JL344
CC BY-SA 3.0
2012-07-27T02:08:28.553Z
2012-07-27T02:08:28.553Z
JL344
<p>Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra's algorithm</a> that solves this problem.</p>

<p>Naturally, this graph can be considered as a resistive network where each edge $e$ with distance (or a cost) $d_{e}$ corresponds to a resistor with resistance $d_{e}$ or conductance $1/d_{e}$. From a physical point of view, assume that we send one unit of current from s to t, say by attaching $s$ to a current source and $t$ to ground. It will induce a certain electric flow in $G$ and this flow is unique. And the approximated solution (or the approximate electric flow) can be obtained in time $\tilde{O}(m)$ where $m$ is the number of edges in the graph.</p>

<p><strong>My question</strong>: what is the relation between the shortest path in a graph and the path in an electric network where the max electric current flows? Is it true that two paths are always the same when there exists a unique shortest path from $s$ to $t$?</p>

<p><strong>The intuition</strong>: The electric current tends to flow through the path with the least resistance, and the least resistance between $s$ to $t$ may be interpreted as the shortest path between $s$ to $t$. </p>

<hr>

<p><strong>updated</strong></p>

<pre><code>8--R--7--R--+
|     |     |
|     R     |
|     |     |
+--R--6--R--+
|     |     |
|     R     |
|     |     |
+--R--5--R--+
|     |     |
|     R     |
|     |     |
+--R--3--R--4
|     |     |
|     R     |
|     |     |
+--R--2     R
|           |
|           |
|           |
+--R--1--R--0
</code></pre>

<p>@MarzioDeBiasi: Thank you for the picture and actual current computation. But ironically, your answer only fortifies my conjecture about the shortest path and max current path. (I apologize for not explaining my conjecture clearly if that causes some confusion.)</p>

<p>As you pointed out, we have the current of 33.9 mA from 4 to 0, but that's due to the superimposition of many currents. For example, the current flows 8 - 2 - 3 - 4 - 0, 8 - 3 - 4 - 0, 8 - 5 - 6 - 7 - 4 - 0 and 8 - 7 - 4 - 0 contribute to the current flow from 4 to 0. And none of them are larger than the curent of 25mA on the path of 8 - 1 - 0. On the other hand, there's only one path for the flow 8 - 1 - 0 and it sends the largest amoun of current in the circuit.</p>

CC BY-SA 3.0
2012-07-25T12:55:09.733Z
I think that using the Ohm's law you can make the path with least resistance arbitrarily long: suppose that $s$ and $t$ are directly connected with a resistor $R$; then you can make another path $P$ from $s$ to $t$ using $n-1$ "segments", with each segment having $n$ resistors in parallel. The total resistence of $P$ is $(n-1)(R/n) = R-R/n < R$. Perhaps a better model is a [flow network](http://en.wikipedia.org/wiki/Flow_network).
Marzio De Biasi
CC BY-SA 3.0
2012-07-25T13:39:23.760Z
@MarzioDeBiasi: But we usually assume that there's no parallel edges in a weighted graph when we analyze the shortest path problem. What if there's no parallel edges or no parallel resistors between any two nodes?
Federico Magallanez
CC BY-SA 3.0
2012-07-25T15:47:50.657Z
ok, do you allow the following 4 edges: $n_1 \leftarrow^R \rightarrow n_A$; $n_A \leftarrow^R \rightarrow n_2$, $n_1 \leftarrow^R \rightarrow n_B$,   $n_B \leftarrow^R \rightarrow n_2$ ? (in this case the reason above is still valid)
Marzio De Biasi
CC BY-SA 3.0
2012-07-25T17:12:35.757Z
@MarzioDeBiasi: Maybe I miss something in your comment, but I guess you are talking about a square-like graph with four edges and four nodes where all the edges have the same weight, which have two shortest paths $n_1 − n_A − n_2$ and $n_1 − n_B − n_2$ of length $2R$. But I'm not sure how it works as a counterexample of my conjecture about the shortest path and the max current path.
Federico Magallanez
CC BY-SA 3.0
2012-07-27T03:02:12.390Z
Your claim that "there is only one path for the flow 8-1-0" is simply not true.  Let $x\flat$ denote the node just to the left of node $x$ in your picture, and consider the path 8-7-6-$6\flat$-$5\flat$-5-3-2-$2\flat$-$1\flat$-1-0.  Yes, the flow through this path also contributes to the current through 1-0.
Jeffε
CC BY-SA 3.0
2012-07-27T16:52:15.823Z
@JɛﬀE: I've even further updated my circuit diagram to distinguish the edges with resistance from those without any resistance. There can be no current flow from 6 to 6♭ as the electric potential at 6 is lower than that of 6♭. (In fact, 6♭ has the same electric potential as 8 because 8 and 6♭ is connected by a wire without any resistance.) And there can be no electric flow from 6♭ to 5♭ because both nodes have the same electric potentia
Federico Magallanez
<graph-theory><co.combinatorics><spectral-graph-theory><shortest-path>
In a resistor network, is there any relation between the shortest path and the maximum electric current path?
Federico Magallanez
# In a resistor network, is there any relation between the shortest path and the maximum electric current path?

(Asked by: username_0 on 2012-07-25)

Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as Dijkstra's algorithm that solves this problem.
Naturally, this graph can be considered as a resistive network where each edge $e$ with distance (or a cost) $d_{e}$ corresponds to a resistor with resistance $d_{e}$ or conductance $1/d_{e}$. From a physical point of view, assume that we send one unit of current from s to t, say by attaching $s$ to a current source and $t$ to ground. It will induce a certain electric flow in $G$ and this flow is unique. And the approximated solution (or the approximate electric flow) can be obtained in time $\tilde{O}(m)$ where $m$ is the number of edges in the graph.
My question: what is the relation between the shortest path in a graph and the path in an electric network where the max electric current flows? Is it true that two paths are always the same when there exists a unique shortest path from $s$ to $t$?
The intuition: The electric current tends to flow through the path with the least resistance, and the least resistance between $s$ to $t$ may be interpreted as the shortest path between $s$ to $t$. 

updated
8--R--7--R--+
|     |     |
|     R     |
|     |     |
+--R--6--R--+
|     |     |
|     R     |
|     |     |
+--R--5--R--+
|     |     |
|     R     |
|     |     |
+--R--3--R--4
|     |     |
|     R     |
|     |     |
+--R--2     R
|           |
|           |
|           |
+--R--1--R--0

@MarzioDeBiasi: Thank you for the picture and actual current computation. But ironically, your answer only fortifies my conjecture about the shortest path and max current path. (I apologize for not explaining my conjecture clearly if that causes some confusion.)
As you pointed out, we have the current of 33.9 mA from 4 to 0, but that's due to the superimposition of many currents. For example, the current flows 8 - 2 - 3 - 4 - 0, 8 - 3 - 4 - 0, 8 - 5 - 6 - 7 - 4 - 0 and 8 - 7 - 4 - 0 contribute to the current flow from 4 to 0. And none of them are larger than the curent of 25mA on the path of 8 - 1 - 0. On the other hand, there's only one path for the flow 8 - 1 - 0 and it sends the largest amoun of current in the circuit.

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory, shortest-path

> **Comments:**
> **username_1**: I think that using the Ohm's law you can make the path with least resistance arbitrarily long: suppose that $s$ and $t$ are directly connected with a resistor $R$; then you can make another path $P$ from $s$ to $t$ using $n-1$ "segments", with each segment having $n$ resistors in parallel. The total resistence of $P$ is $(n-1)(R/n) = R-R/n < R$. Perhaps a better model is a [flow network](http://en.wikipedia.org/wiki/Flow_network).  
> **username_0**: @MarzioDeBiasi: But we usually assume that there's no parallel edges in a weighted graph when we analyze the shortest path problem. What if there's no parallel edges or no parallel resistors between any two nodes?  
> **username_1**: ok, do you allow the following 4 edges: $n_1 \leftarrow^R \rightarrow n_A$; $n_A \leftarrow^R \rightarrow n_2$, $n_1 \leftarrow^R \rightarrow n_B$,   $n_B \leftarrow^R \rightarrow n_2$ ? (in this case the reason above is still valid)  
> **username_0**: @MarzioDeBiasi: Maybe I miss something in your comment, but I guess you are talking about a square-like graph with four edges and four nodes where all the edges have the same weight, which have two shortest paths $n_1 − n_A − n_2$ and $n_1 − n_B − n_2$ of length $2R$. But I'm not sure how it works as a counterexample of my conjecture about the shortest path and the max current path.  
> **username_2**: Your claim that "there is only one path for the flow 8-1-0" is simply not true.  Let $x\flat$ denote the node just to the left of node $x$ in your picture, and consider the path 8-7-6-$6\flat$-$5\flat$-5-3-2-$2\flat$-$1\flat$-1-0.  Yes, the flow through this path also contributes to the current through 1-0.  
> **username_0**: @JɛﬀE: I've even further updated my circuit diagram to distinguish the edges with resistance from those without any resistance. There can be no current flow from 6 to 6♭ as the electric potential at 6 is lower than that of 6♭. (In fact, 6♭ has the same electric potential as 8 because 8 and 6♭ is connected by a wire without any resistance.) And there can be no electric flow from 6♭ to 5♭ because both nodes have the same electric potentia  

---

## 2 answers

### Answer by username_1 on 2012-07-25. Score: 7

**Just an extended comment to include the picture**: if the following (random) resistor network is valid then the max current flow 33.9mA is not on the shortest path from $s$ (+5V) to $t$ (GND).

![enter image description here](https://i.sstatic.net/OE4Ks.jpg)

> **Comments:**
> **username_0**: I updated my question, and apologize for not explaining my conjecture clearly if that caused some confusion.  

---

### Answer by username_3 on 2012-07-27. Score: 5

Your intuition is in a certain sense correct. By straightforward linear
algebra we can find the electric potential of each node in the
graph, given the net current from source to sink.

Now we can calculate the probability distribution of the path taken
by the electric current through the graph. By the second law of thermodynamics,
(that no process may independently cause a decrease in entropy,) it
is impossible for electric current to independently flow from a lower
to a higher potential, and even by the first law (conservation of
energy,) it is impossible for current to flow between nodes of equal
potential through a non-zero resistance. So every edge in the graph
is directed from a higher to a lower potential, any edges of zero resistance are identified to a single node, and any non-zero-resistance edges between
nodes of equal potential are eliminated. Thus the graph is [directed
and acyclic](http://en.wikipedia.org/wiki/Directed_acyclic_graph), and the path taken by the electric current from the source
node to the sink node is a finite [Markov chain](http://en.wikipedia.org/wiki/Markov_chain),
because we are confident that an electric current will take an independent
and memoryless path through the given graph.

The Markov transition probability of each edge in the graph is then
given by the ratio of the current through that edge to the total (gross, not net!) current flowing out from the same node:

$$P(T\_{ij})=
\frac{(I\_{ij})\_+}{\sum\_k (I\_{ik})\_+}=
\frac{\frac 1 {R\_{ij}}(E\_{i}-E\_{j})\_{+}}{\sum\_{k}\frac 1 {R\_{ik}}(E\_{i}-E\_{k})\_{+}}$$

where we have denoted the [positive part](http://en.wikipedia.org/wiki/Positive_and_negative_parts) of a parenthesized expression
by a subscript "+". If we compute the [self-information](http://en.wikipedia.org/wiki/Self-information) of each
edge

$$S(T\_{ij})=-\log P(T\_{ij})$$

then the shortest path weighted additively by self-information is indeed the
most likely path taken by the electric current, and **the current that
actually traverses that entire path** is equal to the total current times the product of the Markov transition probabilities of all the edges along that path.

However, as to your question the shortest path weighted by Markov self-information is not necessarily the shortest path weighted by resistance, (because of the effects of "crowding out" by current taking other paths sharing the same edge.)

> **Comments:**
> **username_0**: I know that there's a close relation between current flow and markov chain probability which is pointed out in the book by Snell and Doyle. But I'm not sure what you mean by 'crowding out'. Can you give a reference which explains crowding out?  
> **username_3**: It's just my way of trying to explain that the current actually traversing a complete path under a Markov chain analysis may well be less than the minimum of the total currents for each edge on the path.  The term "crowding out" as I have used it is very non-technical, not a specific term that can be referenced in the literature.  Sorry if that confused you.  

---

