# Find paths in a graph that any 2 vertices can be reached through N of them

Given a undirected weighted graph. I would like to find a finite set of paths (consecutive vertices and edges)

1. each shorter than L

2. any two vertices can be reached through at most N(in my case N=4) such paths.(paths can be linked halfway, i.e. not necessarily through the begin/end vert).

and the total length of my path set is as small as possible.

In general, I'd like to know if there are relevent theories or algorithms that I can apply to my specific data set.

Thanks in advance for any thought or direction!

• The set of all maximal geodesic paths will certainly do this but there are many. A smaller set is a set of geodesics joining any pair of vertices. $L=N$ is in both cases the diameter. – Roland Bacher May 29 '15 at 11:40