We propose a hierarchical algorithm for approximating shortest paths between all pairs of nodes in a large scale network. The algorithm begins by extracting a high level subnetwork of relatively long links (and their associated nodes) where routing decisions are most crucial. This high level network partitions the shorter links and their nodes into a set of lower level subnetworks. By fixing gateways within the high level network for entering and exiting these subnetworks, a computational savings is achieved at the expense of optimality. We explore the magnitude of these tradeoffs between computational savings and associated errors both analytically and empirically with a case study of the Southeast Michigan traffic network. An order of magnitude drop in computation times was achieved with an on-line route guidance simulation, at the expense of less than 6% increase in expected trip times.