MY194954A - Topological graph optimal path algorithm with constraint conditions - Google Patents

Abstract

Disclosed is a topological graph optimal path algorithm with constraint conditions, comprising: (S10) Generating topological nodes with telecommunication devices and generating topological links with fiber connections, so as to form a topological matrix; (S20) selecting a source and a destination topological node; (S30) establishing, according to the constraint conditions, a list of topological nodes and topological links, which must be passed through, converting the topological links, which must be passed through, into topological nodes, which must be passed through, and adding same to the list of topological nodes which must be passed through; (S40) establishing, according to the constraint conditions, a list of topological nodes and topological links to be avoided, and updating the topological matrix; (S50) setting a start and an end topological node during the current path-searching to be Nt and Ne; when Nt is connected with the topological link L<t?e>, (S60) adding Nt, Ne, and L<t?e> to the overall path; otherwise, (S70) searching for the optimal path between Nt and Ne and adding same to the overall path; and (S80) if Ne is the destination topological node, then ending; otherwise, (S90) updating the topological matrix according to the optimal path between Nt and Ne, and starting the next iteration. The present invention realizes searching for the optimal path under constraint conditions, and improves the path-searching efficiency in the case of a large source topological node degree by improving the Dijkstra algorithm. (Fig. 1)