[Routing] A-Star meet-in-the-middle

Robert (Jamie) Munro rjmunro at arjam.net
Tue Nov 20 17:56:26 GMT 2007

Hash: SHA1

Jon Bright wrote:
> Hi,
> Robert (Jamie) Munro wrote:
>> Is there a reason you can't route by doing 2 A-stars simultaneously, one
>> from the start and one from the destination, and stop when the 2 meet?
> This doesn't (I think) work.  A* might reach a given node X, but it has 
> no idea whether the route it has found to that node is the shortest 
> route to that node.  So your two A*s might meet at a given node, but 
> you're still none the wiser about whether that's the shortest route, 
> because you don't know whether the two routes you have are the shortest 
> route to the meeting node.

> What you should be able to do, though, is to start from source and 
> destination at the same time and whenever these meet, add the 
> from-destination routes, reversed, to the end of the from-source routes 
> which meet that node.  One such route has good chances of turning out to 
> be the shortest - and by working in this way, you'll likely discover 
> that route more quickly.  Worth trying, anyway.

I think that's what I meant - I don't understand your objection above. :-)

Robert (Jamie) Munro
Version: GnuPG v1.4.6 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org


More information about the Routing mailing list