Re: need algorithm for traversing network

One simple algorithm:  (Not sure what it's name is)

(Simplified version where nodes are in a perfect grid)

Starting with the condition where 1 is the starting block
and A is the target

1***
****
****
***A


Number all points next to 1 with a 2, then all points (not already
asigned a number) a 3, etc.  Until you find A

12**
22**
****
***A

Then:

123*
223*
333*
***A

then:

1234
2234
3334
444A

Then simply backtrack 4-3-2-1.


For systems where the interconnections/pipes are not the same length
then the distance traveled to each node should be used,  and numbers
should be assigned to all adjacent nodes IF the number being assigned
is less than the number already assigned to the given node.  (Floating
point values may be required in real world cases)   The structure the
data is in isn't critical so long as finding all connected/adjacent
nodes is easy.

I've see this implemented in java for demonstrating automatic routing
for circuit boards.  A search may turn up more.

-Tim

On Tue, 18 Nov 2003 10:29:24 +0000 (UTC), "Yang Lee"
<[EMAIL PROTECTED]> wrote:

>Hi,
> I have a network of pipes and nodes.
>e.g.     D   
>         0-------0 L
>   B    C|       |
>   0-----0-------0 E
>   |       F     |G      H    I
>---0-------0-----0-------0----0
>   A       |             |
>           0-------------0
>           J             K
>Now I want to get the min length from node
>A to L. Now here multiple possibilities
>are there e.g
>1. A B C D L
>2. A F G E L
>3. A F G E L
>4. A F J K H G E L
>
>So application should generate all these possibilities
>and find the min length route .(each pipes has different
>lengths).  I dont know how to generate these possibilities.
>
>On MSM dave braumbaugh has one artical and JMDL depending on
>genetic algoritm. but its for way too complex network.
>In java memory management will allow to build application
>according to his concept but I am doubtful about MDL.
>Hard to get how to achieve this in MDL.
>
>right now what i do is i start from a point and aplication
>will travel the network . I keep an array /linklist to
>keep the record of already travelled pipes and nodes so next time
>they wont  travelled . I have done this in order to prevent
>infinite loop in case of parallel network. But this alogoritm
>doesn't give perfect min length. if perfect min path pipes 
>and nodes are laid first in a dgn file then it's OK but its not the 
>case most of the time.
>
>i start from a point travel pipe at the end of it place fence
>on the node then after that get the no of pipes exculding
>the host pip then i start with each pipe finish its path in the
>same algoritm and then go for next pip. this is kind of tree
>traversal. but this is not giving perfect result.
>
>So champs please have some feedback for me and reduce my restlesness
>a bit.
>
>Thanks lee.
>
>
>
>-- 
>Posted via Mailgate.ORG Server - http://www.Mailgate.ORG