What is a fast and stable random path algorithm in a node graph?

Question

I have a graph that consists of nodes, and I need a fast algorithm that generates a random path between two nodes. I developed several algorithms for this from scratch, but it seems that not everything is correct.

Either the algorithm gets stuck in a loop, or when I record visited nodes, it sometimes gets stuck between visited nodes. Another issue that I ran into is that my algorithm was too performance unstable.

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

Answer 1

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

• Note that finding this subset of U easy and can be done linearly using DFS or BFS at the back edges of the target.

Using this subset, create a graph G'=(U,E') , where U defined above, and E' = E [intersection] UxU [These edges, but apply only to vertices in U ].

Run a randomized (choosing which vertex to explore next randomly) DFS on G' , until you reach the goal.

• Note. The idea is to find a path - not necessarily a simple one, and therefore you should not support the visited set.
• You can add the “break” rule, which, if you reach a certain depth, you will look for a goal - non-randomized, to avoid endless cycles in circles.
• Perofrmance is expected to be different, as it is linear in the length of the path found, which can be very long or very short ...

Answer 2

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

Answer 3

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

My wild hit is in a dark, pseudo-code, suggesting that the target is accessible 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 amit reservations are saved here:

• You can add the “break” rule, which, if you reach a certain depth, you will look for a goal - non-randomized, to avoid endless cycles in circles.
• Perofrmance is expected to be different, as it is linear in the length of the path found, which can be very long or very short ...