TOPOLOGICAL GRAPH OPTIMAL PATH ALGORITHM WITH CONSTRAINT CONDITIONS

Title:

TOPOLOGICAL GRAPH OPTIMAL PATH ALGORITHM WITH CONSTRAINT CONDITIONS

Document Type and Number:

WIPO Patent Application WO/2017/045578

Kind Code:

A1

Abstract:

Disclosed is a topological graph optimal path algorithm with constraint conditions, comprising: generating topological nodes with telecommunication devices and generating topological links with fibre connections, so as to form a topological matrix; selecting a source and a destination topological node; 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; establishing, according to the constraint conditions, a list of topological nodes and topological links to be avoided, and updating the topological matrix; 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, adding Nt, Ne, and L to the overall path; otherwise, searching for the optimal path between Nt and Ne and adding same to the overall path; and if Ne is the destination topological node, then ending; otherwise, 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.

Inventors:

LI SHU (CN)
SUN HANFU (CN)
WU PING (CN)

Application Number:

PCT/CN2016/098777

Publication Date:

March 23, 2017

Filing Date:

September 13, 2016

Export Citation:

Click for automatic bibliography generation Help

Assignee:

FIBERHOME TELECOMMUNICATION TECH CO LTD (CN)

International Classes:

H04L12/721

Foreign References:

CN105141524A	2015-12-09
CN101621721A	2010-01-06
CN104468356A	2015-03-25
CN101001102A	2007-07-18

Other References:

QIAN, JIN ET AL.: "Breadth First Relax Algorithm for Multi-Constrained Optimal Pat", APPLICATION RESEARCH OF COMPUTERS, 31 January 2007 (2007-01-31), pages 90 - 93