Chips -- you may be underestimating a little bit how powerful your algorithm is.
I'd need to see the whole program before I could offer "correct" commentary, but it's my impression your algorithm works like this:
1. Populate the queue with the Root System (Li01 in your test), mark it as visited, and mark its Parent as 'null'.
2. Pull the first system from the queue. (This is initially just the Root System, but by the time you return to this point, the queue will have been populated, below.) This is the "Current System." Print its path by recursively iterating its parents, parents' parents, etc., until you reach the root system with its 'null' parent.
3. For each system to which the "Current System" connects, do the following:
<pre><font size=1 face=Courier>
- if it has been visited, return to #3 and get the next connected system.
- it hasn't been visited, so proceed: first, tell it who its parent is
- then add it to the queue
- then mark it as visited
</font></pre>
(end of #3 loop: you've iterated over all the Current System's children. Proceed back to #2.)
(end of #2 loop: the queue is empty: you've exhausted possible destinations.)
This a textbook "breadth first" search, perfectly represented here -- very nicely done. Good job combining the search with the printing; good job with recursion also.
The "breadth first" search has a number of virtues, but I'll only name two that a person might have trouble conceptualizing.
==
You're always going to get the shortest path. (Or, more precisely, you're always going to get "a" shortest path. We say this because two shortest paths can be the same length, and this algorithm will choose one of those shortest paths arbitrarily. Which one is chosen will depend on the order in which a parent names its children, which is arbitrary.)
We define "shortest path" for this application as "fewest systems traversed." It's possible for "fewest systems" to take up more time, depending on tradelanes and gate/hole distance (intra-system travel time). But for this application we're ignoring intra-system search, which is a separate search altogether.
If you visualize what you're doing -- look at it from the right perspective -- it will become clear that you're guaranteed to get the shortest-path.
1) The first thing you do: you're adding each system directly connected to the root. (These are called the "children" of the root.) You know that you have the shortest path to those children because the distance is 1.
2) Second you're adding each child system directly connected to those you gathered in #1. (The children of the root's children, if you like: the root's grandchildren.) Their distances are 2. The only way their distance could be less is if the root connected to them directly. But you know it does not because you already checked all the systems it connects to.
3) Third you're adding each child of those you gathered in #2. (The root's great-grandchildren if you like.) Their distances are 3. The only way their distance could be less is if the root connected to them directly, or the root's children connected to them. But you know neither situation is the case, because you already checked the root and you already checked all of its children.
Abstract the general pattern and you'll see that whenever you add a system to the queue, you could not have added it any sooner. You always get the shortest path.
==
One-way connections are no problem. The algorithm is already perfectly sensitive to this issue.
To add a child, you ask the parent what children it connects to. You never ask the child if it connects to the parent. Thus, whenever you traverse a one-way connection, you're traversing it in the correct direction. The missing reverse-connection never becomes an issue, simply because it's not considered a connection.
==
Please do forgive me if at any point I'm belaboring the obvious. Once you get good at this stuff, the above becomes
relatively obvious. But when you're learning it can be genuinely mysterious, a learning process filled with exciting "Ah ha! That's why it works" moments.
Edited by - breslin on 9/21/2007 6:19:28 AM
Wed Sep 19, 2007 8:46 pm 
;
