Thanks for the options. Norman's style of approach might be a good first order approximation - pleasant results but wouldn't take the building into account (if I understand it correctly). The approaches suggested by Ashaman and Oolala are similar for me. I can't do a full offline calculation because we're using procedural level generation (sorry I didn't mention!). But we can construct a graph in terms of rooms and corridors, so a certain level of precalculation on a graph level may be possible.
Any other options would also be welcome!