In this paper, the multi-objective trajectory planning problem for an unmanned aerial vehicle on a low altitude terrain following/threat avoidance mission is studied. Using a grid-based discrete scheme, the continuous constrained optimization problem into a combination of search and decision problem is transformed over a finite network. A variant of the minimum cost network flow approach, which is referred to as label-setting greedy-based algorithm, is then applied to this problem. Using the digital terrain elevation data and discrete dynamic equations of motion, an optimal four-dimensional trajectory (three spatial and one time dimensions) from a source to a destination is obtained deterministically by minimizing a nonlinear cost functional subject to dynamic and mission constraints of the unmanned aerial vehicle. For each arc in the grid, a cost functional is considered as a combination of the path length, fuel consumption, flight time, and risk-of-threat region. Moreover, due to the increasing deviation of inertial navigation system in terms of time, having a safe flight and collision avoidance with terrain at low altitude is a significant problem in the trajectory design of this type of the vehicles. In this work, it’s tried to meet this constraint in the trajectory planning. The simulation studies on the unmanned aerial vehicle flight planning problem are presented to verify the capability of the proposed algorithm to generate admissible trajectory in minimum possible time comparison to previous works.