A new space era is bringing de-ployments of thousands of networked assets in near-Earth and deep-space. Delay-Tolerant Networking (DTN) protocols and algorithms such as Contact Graph Routing (CGR) are state-of-the-art technologies certainly capable of achieving this ambitious objective. Never-theless, in this paper, we highlight and analyze the roots of current scalability limits of CGR, to then propose more efficient altatives. In particular, we leverage a different graph mod-eling approach that enables optimizations such as priority queues and spanning-tree searches in the core route determination process. While such abstract data types are difficult to adapt to CGR, we incorporate them into a novel Shortest-Path Tree Approach for Routing in Space Networks (SPSN), which is presented as a compute-efficient altative. This paper thoroughly describes the SPSN approach in-cluding route object modeling, capacity-ori-ented search, and potential route management techniques. Prototype evaluations analyzed in this paper present significant evidence that SPSN outperforms legacy CGR in more than an order of magnitude in contact plans com-prising thousands of contacts.