When I first looked at this a few years ago, all I could really find was the "Channel" router algorithm. It was "as plain as day" that the "normal" auto-router was based on shortest path (or some variant), but not much was published.
The Channel Router
The Channel router is certainly an interesting problem. I looked at it for routing strip-board. Here is the concept, layout your components either side of a "channel" and the Channel router will link them up. Here is my proposed strip-board layout:
Note: the ICs can be replaced with individual components.
And here a typical "channel" wiring diagram:
Note: The Channel algorithm has been modified to suit the strip-board constraint of one wire join per location (or hole).
So it is possible to auto-route strip-board efficiently (from an algorithm point of view) but it is not that elegant (visually).
It might have a niche if the parts are also auto-placed. But at that point I did not feel as if this was going to be a "useful" project to continue.
The shortest path algorithm is well known and I have used it n the past to determine truck haulage paths of open pit mines (yes I was a mining consultant in a past life). Here is an example (the white traces are the proposed truck haulage paths):
Note: the scale of this problem is quite large (i.e. about 10 km across).
So okay, I have used this algorithm before! So what is so hard about auto-routing?