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: https://i.sstatic.net/O228a.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.

Mechanist

Perhaps this helps you: en.wikipedia.org/wiki/Steiner_tree_problem – Incursion

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. – Mechanist

I find the description a little hard to follow. Could you maybe give a small example graph and solution? – Ascribe

You want all the paths? You want all simple paths containing at least two members of the subset? – Lavona

I've updated the question with an animated gif and hopefully improved description – Mechanist

Nice improvement! New question: what is the actual problem you're trying to solve? Obviously I can't be sure, but searching for every single path (or spanning tree or else) might be very suboptimal. If you really, really need to do what you're describing, then feel free to ignore this question :) – Ascribe

Yet another question: one of the frames from your example gif describes a route that is not really a simple path (this one: imgur.com/0vjvr.png). Are that kind of route (or rather spanning tree) allowed as a valid solution for your problem? – Ascribe

The problem i'm trying to solve is guaranteeing a passage over a terrain im creating. I start with a blank area divided into a grid, at certain points on the outer edge of the grid you can enter/exit (blue nodes). What i want to do is randomly pick a passage (the subgraph) that connects all these enter exit points. Once i have this "safe passage" i can populate any part of the area not part of the passage with scenery. This is why i need all (or a lot) of possible subgraphs so that i can have variety in how you traverse the terrain .The path you pointing out would be a valid solution for this. – Mechanist

Answer 1

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

Ascribe

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

Novelette

Answer 3

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

Ascribe

This is closest to what i'm looking for, however if i understand correctly a spanning tree includes all of vertices of the graph. I also looked at "K-minimum spanning tree" but that appears to be for looking for spanning trees that contain a certain number of vertices rather than a tree connecting specific set of vertices. – Mechanist

You're right about that, but it should not be too hard to specialize the algorithms so that they only take your vertices-of-interest into account, rather than all of them. Even if this requires you to modify the algorithms, the upside is that your problem should be easier than the general one. I might give this is shot myself for the fun of it, if you like (and if I find the time). – Ascribe