Graph Algorithm To Find All Paths Between N Arbitrary Vertices

6
votes

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.

3
algorithmlanguage-agnosticgraphgraph-theorysubgraph
Perhaps this helps you: en.wikipedia.org/wiki/Steiner_tree_problem – Philip Daubmeier
I hadn't seen that. However I can't add vertices to the graph as i am using the graph to represent something that is physical and can't be modified, so i don't think it is applicable. – russtbarnacle
I find the description a little hard to follow. Could you maybe give a small example graph and solution? – Jakob
You want all the paths? You want all simple paths containing at least two members of the subset? – Beta
I've updated the question with an animated gif and hopefully improved description – russtbarnacle

3 Answers

1
votes

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

1
votes

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

1
votes

There are so many ways to approach this and in order not confuse things, here's a separate answer that's addressing the description of your core problem:

Finding ALL possible subgraphs that connect your blue vertices is probably overkill if you're only going to use one at a time anyway. I would rather use an algorithm that finds a single one, but randomly (so not any shortest path algorithm or such, since it will always be the same).

If you want to save one of these subgraphs, you simply have to save the seed you used for the random number generator and you'll be able to produce the same subgraph again.

Also, if you really want to find a bunch of subgraphs, a randomized algorithm is still a good choice since you can run it several times with different seeds.

The only real downside is that you will never know if you've found every single one of the possible subgraphs, but it doesn't really sound like that's a requirement for your application.

So, on to the algorithm: Depending on the properties of your graph(s), the optimal algorithm might vary, but you could always start of with a simple random walk, starting from one blue node, walking to another blue one (while making sure you're not walking in your own old footsteps). Then choose a random node on that path and start walking to the next blue from there, and so on.

For certain graphs, this has very bad worst-case complexity but might suffice for your case. There are of course more intelligent ways to find random paths, but I'd start out easy and see if it's good enough. As they say, premature optimization is evil ;)