Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
An undirected acyclic graph is a disjoint collection of trees, so the number of shortest paths from s to t is either 1 or 0 depending on whether s and t are in the same connected component or not. However, since you mention grid graphs (which have many cycles!) maybe you want to edit your question. –  Ryan Williams May 25 '10 at 3:02
    
I guess Eduardo means loop-free graphs. –  Hans Stricker May 25 '10 at 6:12
add comment

2 Answers 2

up vote 1 down vote accepted

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).

share|improve this answer
    
Shouldn't P(s,d,t)=P(s,t)*P(d,t)? –  Kevin Ventullo May 25 '10 at 3:09
    
Yes it should. Thanks, I fixed it. –  Douglas S. Stones May 25 '10 at 5:58
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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