In this paper, based on graph theory and multi-objective optimization theory, the trajectory planning problem of maritime drones is studied. A mathematical model is established using directed graphs, with the objectives of minimizing the trajectory length and the number of corrections. Different from previous algorithms, this paper refers to the idea of the A-star algorithm and combines dynamic labeling and non-dominated sorting strategies to propose an efficient heuristic algorithm: the multi-objective path planning algorithm based on forward labels. The result of this algorithm is a set of Pareto optimal solutions, which require further selection using an ideal point-based best compromise solution method to obtain the best compromise plan. In addition, this paper conducts a comparative study with the NSGA-II algorithm, verifying the effectiveness and superiority of the proposed algorithm. The results show that the algorithm in this paper can quickly obtain the best compromise solution.