Skip to main content
2 of 2
acyclic -> cyclic

Maximum number of shortest-paths

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.