I can see a number of ways this might be done, but before I go off writing my own plugin, I was hoping that perhaps someone has written one already?
[Edit] Also, a paging library would be a nice thing to have.
A* Pathfinding Project Pro
This is probably the most complete with ongoing development. They also have a free version as well.
I think that the Astar Pathfinding Project has such a feature. You could take a look at it to base your own methods on it.