I'm not sure if this is relevant or not, which is why I haven't mentioned it before, but on my forum we discussed a shortest path algorithm a while back:
Effectively you start out with "particles" in your current (start) location and send them out all possible exits (this may not be all directions because of obstacles, lack of doors, etc.). If a location is already visited the particle self-destructs on the basis that it must have taken the slower route to get there. This tends to prune the number of particles down to a manageable number. Eventually one reaches the (desired) exit. Fortunately the particles "have a memory" of the route they took, so by asking the particle, which reached the exit, how it got there, you find the shortest path.
I used the basic concept to make a (MUD game) mapper. Each map is drawn "on the fly" by using this system, except in this case the rooms are drawn with lines connecting them.
The mapper can be used to travel from room A to room B (or the other way, I suppose) by clicking on the destination room. By using the shortest path algorithm it generates the most efficient way of getting there.
It might sound slow, but the mapper draws the entire map (as in the picture above) something like 20 or 30 frames per second (depending a bit on how far it goes before running out of things to map).