  In this paper, we address the problem of path planning for a cellular-enabled
UAV with connectivity and battery constraints. The UAV's mission is to deliver
a payload from an initial point to a final point as soon as possible, while
maintaining connectivity with a BS and adhering to the battery constraint. The
UAV's battery can be replaced by a fully charged battery at a charging station,
which may take some time depending on waiting time. Our key contribution lies
in proposing an algorithm that efficiently computes an optimal UAV path in
polynomial time. We achieve this by transforming the problem into an equivalent
two-level shortest path finding problem over weighted graphs and leveraging
graph theoretic approaches. In more detail, we first find an optimal path and
speed to travel between each pair of charging stations without replacing the
battery, and then find the optimal order of visiting charging stations. To
demonstrate the effectiveness of our approach, we compare it with previously
proposed algorithms and show that our algorithm outperforms those in terms of
both computational complexity and performance. Furthermore, we propose another
algorithm that computes the maximum payload weight that the UAV can deliver
under the connectivity and battery constraints.
