title: How does a Breadth-First Search work when looking for Shortest Path?
body: <p>I've done some research, and I seem to be missing one small part of this algorithm. I understand how a Breadth-First Search works, but I don't understand how exactly it will get me to a specific path, as opposed to just telling me where each individual node can go. I guess the easiest way to explain my confusion is to provide an example:</p>
  <p>So for instance, let's say I have a graph like this:</p>
  <p><img src="https://i.stack.imgur.com/e9PxE.jpg" alt="enter image description here" /></p>
  <p>And my goal is to get from A to E (all edges are unweighted).</p>
  <p>I start at A, because that's my origin. I queue A, followed by immediately dequeueing A and exploring it. This yields B and D, because A is connected to B and D. I thus queue both B and D.</p>
  <p>I dequeue B and explore it, and find that it leads to A (already explored), and C, so I queue C. I then dequeue D, and find that it leads to E, my goal. I then dequeue C, and find that it also leads to E, my goal.</p>
  <p>I know logically that the fastest path is A-&gt;D-&gt;E, but I'm not sure how exactly the breadth-first search helps - how should I be recording paths such that when I finish, I can analyze the results and see that the shortest path is A-&gt;D-&gt;E?</p>
  <p>Also, note that I'm not actually using a tree, so there are no &quot;parent&quot; nodes, only children.</p>