The use of Unmanned Aerial Vehicles (UAVs) is becoming common in our daily lives and cellular networks are effective in providing support services to UAVs for long-range applications. The main target of this paper is to propose a modified form of well-known graph search methods i.e., Dijkstra and A-star also known as Aalgorithm, for quality-aware trajectory planning of the UAV. The aerial quality map of the propagation environment is used as an input for UAV trajectory planning, and the quality metric considered for this work is Signal to Interference plus Noise Ratio (SINR). The UAV trajectory is quantified in terms of three performance metrics i.e., path length, Quality Outage Ratio (QOR), and maximum Quality Outage Duration (QOD). The proposed path planning algorithm aims at achieving a trade-off between the path length and other quality metrics of the UAV trajectory. The simulations are performed using an agreed 3GPP macro cell LOS scenario for UAVs in MATLAB. Simulation results illustrate that the proposed algorithm significantly improves the QOR by slightly increasing the path length compared with the naive shortest path. Similarly, the outage avoidance path achieves high QOR at the expense of large path length, and our proposed method finds a compromise and provides an optimal quality-aware path.