What's a fast and stable algorithm for a random path in a node graph?

Question

I have a graph which consists of nodes and I need a fast algorithm that generates a random path between two nodes. I designed several algorithms from scratch for this but can't seem to get it right.

Either the algorithm gets stuck in loops, or when I keep record of the visited nodes it sometimes gets stuck between visited nodes. Another problem I encountered is that my algorithm was too unstable in performance.

So my question is; does anyone know a fast and stable algorithm for a random path between two reachable nodes in an undirected graph?

Answer 1

Let your graph be G=(V,E). Create a subset U of V such that U = { u | there is a path from u to the target }.

• Note that finding this subset U is easy - and can be done in linear time using DFS or BFS on the reversed edges from the target.

Using this subset, create a graph G'=(U,E') where U is defined above and E' = E [intersection] UxU [The same edges, but applied only on vertices in U].

Run randomized (choosing which vertex to explore next on random) DFS on G' until you reach the target.

• Note - the idea is to find a path - not necesseraly simple, and thus you shouldn't maintain a visited set.
• You might add a "break rule" that if you reach a certain depth, you will seek the target - unrandomised, to avoid infinite loops in circles.
• Perofrmance is expected to be varying, since it is linear in the length of the found path, which might be very long or very short...

Answer 2

If I understand your question correctly, you are trying to generate a uniform spanning tree.

Answer 3

It depends on what you mean by random. If you don't care what it means, have you tried a monte-carlo method?

My wild stab in the dark, pseudo-code, assuming that target is reachable at all, and that you have an undirected graph.

1. s <- start node
2. Choose a random neighbor of s, call that neighbor n.
3. Add the edge from s to n to the path.
4. Set s <- n.
5. Go to 2, unless you've reached the target.

The caveats of amit hold here, too:

• You might add a "break rule" that if you reach a certain depth, you will seek the target - unrandomised, to avoid infinite loops in circles.
• Perofrmance is expected to be varying, since it is linear in the length of the found path, which might be very long or very short...