1
$\begingroup$

Say that we have a 2x2 regular grid or network. We label the nodes 0 to 3 row-wise. Then, for each node, we want to compute the number of shortest paths that pass through them.

I have a Python code for this but first I want to figure out how it works in theory in an easy situation.

So, if you do this calculation by hand, what do you obtain? I get that each node is passed through by 8 shortest paths.

The network:

(0) -  (1)
 |      |
(2) -  (3)

Example for node 1 (upper right corner):

Path 1: 0->1
Path 2: 0->3
Path 3: 1->3
Path 4: 1->2
Path 5: 2->1
Path 6: 3->1
Path 7: 1->0
Path 8: 3->0

So for me the number of shortest paths passing through node (1) is 8. Is this correct?

$\endgroup$

0