StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGraph traversal - finding and returning the shortest distance
text
Body
copied!<p>I am using a Breadth first search in a program that is trying to find and return the shortest path between two nodes on an unweighted digraph.</p> <p>My program works like the wikipedia page psuedo code</p> <p>The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows: Enqueue the root node Dequeue a node and examine it If the element sought is found in this node, quit the search and return a result. Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered. If the queue is empty, every node on the graph has been examined – quit the search and return "not found". If the queue is not empty, repeat from Step 2.</p> <p>So I have been thinking of how to track number of steps made but I am having trouble with the limitations of java (I am not very knowledgeable of how java works). I originally was thinking that I could create some queue made up of a data type I made that stores steps and nodes, and as it traverses the graph it keeps track of the steps. If ever the goal is reached just simply return the steps.</p> <p>I don't know how to make this work in java so I had to get rid of that idea and I moved on to using that wonky Queue = new LinkedList implementation of a queue. So basically I think it is a normal integer queue, I couldn't get my data type I made to work with it.</p> <p>So now I have to find a more basic approach so I tried to use a simple counter, this doesn't work because the traversal algorithm searches down many paths before reaching the shortest one so I had an idea. I added a second queue that tracked steps, and I added a couple counters. Any time a node is added to the first queue I add to the counter, meaning I know that I am inspecting new nodes so I am not a distance further away. Once all those have been inspected I can then increase the step counter and any time a node is added to the first queue I add the step value to the step queue. The step queue is managed just like the node queue so that when the goal node is found the corresponding step should be the one to be dequeued out.</p> <p>This doesn't work though and I was having a lot of problems with it, I am actually not sure why.</p> <p>I deleted most of my code in panic and frustration but I will start to try and recreate it and post it here if anyone needs me to.</p> <p>Were any of my ideas close and how can I make them work? I am sure there is a standard and simple way of doing this as well that I am not clever enough to see.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload