According to the characteristics of genetic algorithm and the Dynamic Sparse A^* Search (Dynamic Sparse A^* Search, DASA) algorithm, this paper puts forward a combinational optimal algorithm fulfilling adaptive path planning in flying environment with unknown threat. Before flight, the ground station adopt genetic algorithm which possess the powerful ability of global search to realize Universal Search, we proceed programme from the starting point to the target point to generate the global optimal or suboptimal feasible reference airline. When the UAV is executing fly missions, DASA algorithm is used for on line route re planning based on the reference flight line as the benchmark. The simulation results show that compared with the genetic algorithm, the combined algorithm cannot only produce an approximate optimal solution, but also meet the requirements of real-time online application.