Path-Finding in Subway Networks

[Ángel Martin]

I've been working on another MCODE project for the last few weeks that it's getting close to completion. It's quite ambitious in that it was totally new for me, so I've had to do some initial research to see how to approach it. The project in question is to find connecting paths in a subway network (or any other kind) so the user can go from station A to station B, regardless of the number of transfers required. That really piqued my curiosity to the point of attempting some leverage with the Dictionary/Country ROMS core routines for table searches, but the core stuff (i.e. the path-finding itself) was a big dark area and I had to develop new tricks to tackle it...

I won't pretend that my implementation is of any ground-breaking importance but I sure am having a ball tangled-up with these pesky concepts, keeps my aging mind (relatively) fit. Certainly much of the literature I checked (Traveling Salesman, Djikstra's algorithm, et al) doesn't lend itself to easy versioning as MCODE).

The first example is the Madrid Metro (all those rides of my youth had to be honored ;-) It's an 8k Module, as the "MAP" part already takes over 3,200 bytes - holding the station names and line topology "coordinates". I've already solved the 1x and 2x- transfer scenarios which cover about 90% of the cases, but the remaining 10% are a tough nut to crack... will let you know when it's ready to see the limelight, although this is a very idiosyncratic module so not likely to create much interest (as if I cared, right?).

Does this strike a chord with anybody out there?

To be continued...