Topological graph optimal route algorithm with constraint conditions

Abstract

The invention discloses a topological graph optimal route algorithm with constraint conditions. The algorithm includes the following steps that: telecommunication equipment is abstracted to topological nodes, and optical fiber connections are abstracted to topological links, and as a result a topological matrix can be formed; a source topological node and a destination topological node are selected; an include topological node list and an include topological link list are established according to the constraint conditions, and include topological links are converted into include topological nodes, and the include topological nodes are added into the include topological node list; an avoid topological node list and an avoid topological link list are established according to the constraint conditions, and the topological matrix is updated; and a starting topological node and a finishing topological node which are routed currently are set as Nt and Ne respectively; when Nt is connected with a topological link<t,e>, Nt, Ne and <t,e> are added into an overall route, otherwise, an optimal route between Nt and Ne is added into the overall route; if Ne is the destination topological node, the method terminates, otherwise, the topological matrix is updated according to the optimal route between Nt and Ne, and next iteration is started. With the topological graph optimal route algorithm of the invention adopted, the optimal route can be searched under the constraint conditions, and routing efficiency when the source topological node has a large degree can be improved through the improved Dijkstra algorithm.

Description

technical field [0001] The invention relates to an optimal path algorithm of a topological graph, in particular to an optimal path algorithm of a topological graph with constraints. Background technique [0002] In the telecommunications transmission network, the telecommunications equipment is the communication node of the network, the optical fiber connects two telecommunications equipments as the communication channel, and many telecommunications equipments are connected to form the entire communication network. [0003] In engineering, when configuring the telecommunication transmission network circuit, it is necessary to find the optimal path from one telecommunication equipment to another telecommunication equipment through the designated telecommunication equipment and optical fiber. In order to solve the problem conveniently, the telecommunication transmission network is abstracted into the form of a topological graph, the telecommunication equipment is used as the t...

AI Technical Summary

Problems solved by technology

[0005] (1) The constraints of the optimal path cannot be specified, that is, the topological nodes and topological links that the optimal path must pass through cannot be specified, and the topological nodes and topological links that the optimal path avoids cannot be specified;

[0006] (2) There is no guarantee that the optimal path will not repeatedly pass through a certain topological node or topological link;

[0007] (3) Define the degree of a topological node as the number of topological links connected to the topological node. When the degree of the source topological node is large, the time to find the optimal path increases significantly, which cannot meet the time requirements of engineering applications

Images