A method for searching the shortest path of must-pass nodes

A method for searching for the shortest path of must-pass nodes, comprising:

• S1. acquiring must-pass nodes and constructing Thiessen polygons according to the must-pass nodes;
• S2. determining whether a start node of the must-pass nodes and an end node of the must-pass nodes are the same must-pass node, if not, performing S3 processing directly;
• S3. starting from a Thiessen polygon where the start node of the must-pass nodes is located, querying Thiessen polygons adjacent to the Thiessen polygon;
• then merging the adjacent Thiessen polygons in the Thiessen polygons adjacent to the Thiessen polygon in sequence into the first merged polygon, and then performing S4 processing;
• if there is a non-adjacent and isolated Thiessen polygon among the queried adjacent Thiessen polygons, performing S5 processing on the non-adjacent and isolated Thiessen polygon correspondingly;
• S4. querying unprocessed Thiessen polygons adjacent to the first merged polygon based on the first merged polygon, and then merging adjacent unprocessed Thiessen polygons in the unprocessed Thiessen polygons adjacent to the first merged polygon in sequence into the second merged polygon;
• if there is a non-adjacent and isolated unprocessed Thiessen polygon in the adjacent unprocessed Thiessen polygons, performing S5 processing on the non-adjacent and isolated Thiessen polygon correspondingly, until all Thiessen polygons are processed;
• S5. if there is a non-adjacent isolated Thiessen polygon in the Thiessen polygons adjacent to the Thiessen polygon where the start node of the must-pass nodes is located, or in the adjacent unprocessed Thiessen polygons of a certain merged polygon, merging the isolated Thiessen polygon with a certain merged polygon with an adjacent common edge, so as to ensure that there are only two adjacent merged polygons in each merged polygon, except the Thiessen polygon where the start node of the must-pass nodes is located and the Thiessen polygon where the end node of the must-pass nodes is located;
• S6. establishing the Denaulay triangle by every must-pass node, and deleting edge lines of two vertices in Denaulay triangle that are not in the same merged polygon;
• S7. if a node degree of remaining edge lines in the merged polygon is not greater than or equal to three, then performing S8, otherwise selecting the shorter edge line according to a principle of closing both sides of graph;
• S8. connecting the edge lines of each merged polygon end-to-end, and the shortest connection line is a result.