What is a good way to implement this path-finding code, without using threads?

Question

In my distributed java class I had to make an algorithm that would solve a maze using threads. All intersections within the maze (more than one remaining path) would create a new thread that would continue where the old one left off. At the end I would look over all the paths, and see which one is valid (started at the beginning, got to the end).

I want to do the same thing with a Ford–Fulkerson algorithm but this time, I don't have to use threads and I'd like to avoid that, since having a thread that just keeps making new threads that make new threads (and so forth) seems unnecessarily dangerous.

Here is my algorithm in pseudo code + some info:

The graph is a n by n matrix where int matrix [line][column] represents the flow between node line index and node column index (un-connected has a flow of -1)

PathFinder:
    current
    start
    end
    path[] // actually an arraylist of integer

    run () { // thread part
        while not at end path {
            if possible paths == 0
               return
            if possible paths == 1
               continue that way
            if possible paths > 1
               create new thread for each path // each thread inherits path up to this point
        }
    }

And in the main program I just call pathFinder(start,end) then PathFinder.getAllPaths(), and filter invalid paths (dead ends, loops). Well actually I plan to handle loops within the run() portion but I forgot to do that yet. It's pretty easy tho.

At the end I have a static variable with all the paths (arrayList). I verify which paths are "valid" and that's that.

Should I make this recursive instead of using threads ? Any other solutions ? Should I post actual code (though it's incomplete).

Answer 1

You could use a queue instead of threads. Each intersection just adds nodes to investigate to the queue, and the main loop keeps running until the queue is empty.

Answer 2

In the end, the suggested answer of using queues was defeating the purpose. If I'd use queues I'd still have to implement some sort of backtracking, the whole point of this is to avoid using backtracking, so I'm going to stick with threads. After some thought, there is no way they could interact in a negative way, thus removing any fear of concurrency issues.