Graph Algorithm To Find All Paths Between N Arbitrary Vertices

Question

I have an graph with the following attributes:

• Undirected
• Not weighted
• Each vertex has a minimum of 2 and maximum of 6 edges connected to it.
• Vertex count will be < 100
• Graph is static and no vertices/edges can be added/removed or edited.

I'm looking for paths between a random subset of the vertices (at least 2). The paths should simple paths that only go through any vertex once.

My end goal is to have a set of routes so that you can start at one of the subset vertices and reach any of the other subset vertices. Its not necessary to pass through all the subset nodes when following a route.

All of the algorithms I've found (Dijkstra,Depth first search etc.) seem to be dealing with paths between two vertices and shortest paths.

Is there a known algorithm that will give me all the paths (I suppose these are subgraphs) that connect these subset of vertices?

edit:

I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: http://imgur.com/mGVlX.gif

There are two stages pre-process and runtime.

pre-process

1. I have a graph and a subset of the vertices (blue nodes)
2. I generate all the possible routes that connect all the blue nodes

runtime

1. I can start at any blue node select any of the generated routes and travel along it to reach my destination blue node.

---

So my task is more about creating all of the subgraphs (routes) that connect all blue nodes, rather than creating a path from A->B.

Answer 1

What you're searching for is (if I understand it correctly) not really all paths, but rather all spanning trees. Read the wikipedia article about spanning trees here to determine if those are what you're looking for. If it is, there is a paper you would probably want to read:

Gabow, Harold N.; Myers, Eugene W. (1978). "Finding All Spanning Trees of Directed and Undirected Graphs". SIAM J. Comput. 7 (280).

Answer 2

A simple breadth-first search will give you the shortest paths from one source vertex to all other vertices. So you can perform a BFS starting from each vertex in the subset you're interested in, to get the distances to all other vertices.

Note that in some places, BFS will be described as giving the path between a pair of vertices, but this is not necessary: You can keep running it until it has visited all nodes in the graph.

This algorithm is similar to Johnson's algorithm, but greatly simplified thanks to the fact that your graph is unweighted.

Time complexity: Since there is a constant number of edges per vertex, each BFS will take O(n), and the total will take O(kn), where n is the number of vertices and k is the size of the subset. As a comparison, the Floyd-Warshall algorithm will take O(n^3).