With the emergence and development in 5G cellular systems and ultra dense networks, recent years have witnessed a surge of interest in Dense Wireless Sensor Network (DWSN) in academia and industry. Although many existing works have explored the Steiner tree problem (STP) like multicast and topology design in WSN scenarios, new challenges introduced by growing node number and redundant links receive much less attention yet. The complexity of the topology usually makes algorithms that find the optimal solution unacceptable in terms of running time. Meanwhile, other approximate algorithms with lower time complexity cause too much performance loss. In this paper, we propose a physarum-based pre-processing algorithm called PBA for boosting up a traditional algorithm that can find STP’s optimal solution. The proposed algorithm could select crucial edges and vertices quickly by imitating the physarum’s foraging process. Our algorithm could eliminate edges and vertices irrelevant to the optimal solution by 80% and 50% in the original graph, respectively. This simplified graph produced by PBA is used in the traditional algorithm for obtaining the final result. PBA could also be transformed into a distributed version with minor changes for large-scale topology. Simulation results demonstrate that the proposed algorithm can shorten the original algorithm’s running time by one to two orders of magnitude with less than 5% performance loss in general.