6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Jul 25, 2012 at 12:55
  • $\begingroup$ @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? $\endgroup$
    – Federico Magallanez
    Jul 25, 2012 at 13:39
  • $\begingroup$ 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) $\endgroup$
    – Marzio De Biasi
    Jul 25, 2012 at 15:47
  • $\begingroup$ @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. $\endgroup$
    – Federico Magallanez
    Jul 25, 2012 at 17:12
  • $\begingroup$ 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. $\endgroup$
    – Jeffε
    Jul 27, 2012 at 3:02

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I updated my question, and apologize for not explaining my conjecture clearly if that caused some confusion. $\endgroup$
    – Federico Magallanez
    Jul 26, 2012 at 22:51
4
$\begingroup$

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, and the path taken by the electric current from the source node to the sink node is a finite 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 of a parenthesized expression by a subscript "+". If we compute the 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.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Federico Magallanez
    Jul 27, 2012 at 19:09
  • $\begingroup$ 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. $\endgroup$
    – JL344
    Jul 27, 2012 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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