Optimization of Overall Shortest Path Planning Algorithm Based on Graph Theory: Multi-Vertex Phased Inspection Algorithm

Graph theory is a powerful tool for addressing problems involving discrete structures, such as determining the shortest length of connected river networks or the shortest distance between connected power stations. For tasks that cannot be completed in a single inspection cycle, it is necessary to divide the work into multiple groups and conduct inspections in phases. In each phase, there is a requirement to return to the origin point. Currently, there is a lack of application software in the market to address such shortest path problems. To solve these practical issues and meet customer demands, the researcher employs methods such as combinatorial number theory, graph theory algorithms, and traversal algorithms. The solution is presented in three forms: algorithmic steps, algorithmic formulas, and application examples. The results demonstrate that the research problem is solvable, the shortest path exists, and the proposed algorithm is feasible. Additionally, to achieve the goal of non-repeating shortest paths, the indegree of each vertex in the shortest inspection path should be 2.