You could have suggested A* that will find shortest routes. The problems is that the time and space is exponential in the path length.
The best solution is probably some hierarchical route finder, finding distances between major intersections and then locally searching from a particular location to these intersections.