Maximum number of shortest-paths

Question

I would like to know if there is a equation for the maximum number of shortest paths that pass through r where r is a node contained in any path from node s (a fixed node, i mean, s is the only source of paths) to any node t in an unweighted undirected acyclic graph. I've searched and found this work that show this number for grid graphs, but I'm interested in this number for general topology graph.

I would be grateful for any reference for a work in this subject, or a suggestion how to start to solve this problem. Thanks in advance.

Edit: Sorry, the graph I'm interested is loop-free as Hans Stricker pointed, but it is cyclic.

Answer 1

Judging from the link you provide, you have three distinct vertices s,t,d and want to compute the number of shortest walks P(s,d,t) from s to d that contain t. The reason I use "walks" instead of "paths" is because of graphs like:

s----d----t

where we must reuse edges.

If you really mean acyclic graph, then P(s,d,t)=1 if there is a path containing vertices s,t and d and P(s,d,t)=0 otherwise.

Let P(s,t) be the number of shortest walks between s and t and P(s,s)=1. If s, d and t are all distinct then P(s,d,t)=P(s,t)P(d,t).

In Section 2.4 of the paper you link to, they describe the algorithm for finding P(s,t). That is $P(s,t)=\sum_{v \in V} P(s,v)$ where V is the set of neighbours of t for which P(s,v) is minimal. The difficulty is identifying which neighbours of t minimise P(s,v).

One way is to construct a set Sn of paths of length n=1,2,... (this can be done recursively), from t until you find some neighbour of s. Then count 1 for each path that ends in a neighbour of s and 0 otherwise. Another way would be to compute P(s,t) and then use a backtracking algorithm.

There's not going to be an exciting formula for P(s,d,t) in general, since it depends on the graphs' structure. This is much like how there's not going to be an exciting formula for the number of edges in a graph (unless you restrict to some specific class of graphs).

Answer 2

I do not see the interest of introducing $r$. The number of shortest paths from $s$ to $t$ passing through $r$ is the product of the number of shortest paths from $s$ to $r$ times the number of shortest paths from $r$ to $t$ if $d(s,t)=d(s,r)+d(r,t)$ and is zero otherwise.

It is thus enough to have formulae for the number of shortest paths between two given vertices $x,y$. This number is of course the coefficient with indices $x,y$ in $A^d$ where $d$ is the distance between $x$ and $y$ and where $A$ is the adjacency matrix (and $d$ is also defined as smallest natural integer such that the coefficient with indices $x,y$ in $A^d$ is non-zero).