We address the path planning problem for a cellular-enabled unmanned aerial vehicle (UAV) considering both connectivity and battery constraints. The UAV's mission is to expeditiously transport a payload from an initial point to a final point, while persistently keeping the connection with a base station and complying with its battery limit. At a charging station, the UAV's depleted battery can be swapped with a completely charged one. Our primary contribution lies in proposing an algorithm that outputs an optimal UAV trajectory with polynomial computational complexity, by converting the problem into an equivalent two-level graph-theoretic shortest path search problem. We compare our algorithm with several existing algorithms with respect to performance and computational complexity, and show that only our algorithm outputs an optimal UAV trajectory in polynomial time. Furthermore, we consider other objectives of minimizing the UAV energy consumption and of maximizing the deliverable payload weight, and propose algorithms that output an optimal UAV trajectory in polynomial time.