The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jun. 18, 2013
Filed:
Sep. 02, 2009
Dajiang Wang, Shenzhen, CN;
Zhenyu Wang, Shenzhen, CN;
Dajiang Wang, Shenzhen, CN;
Zhenyu Wang, Shenzhen, CN;
ZTE Corporation, Shenzhen, CN;
Abstract
The present invention discloses a method and apparatus for implementing a K-shortest paths algorithm in a condition of multiple sides between adjacent nodes. The implementing method comprises: recording original topology information into a topology structure; adding one virtual node into each of the original sides other than the one with the shortest weight between the two nodes respectively to divide each of the original sides except for the original side with the shortest weight into two new sides, a weight of the new side being obtained by splitting a weight of the original edge where the new side locates; according to new topology information after adding virtual nodes, calculating K-shortest paths between designated nodes; and checking each path in the calculated K-shortest paths in sequence: reinstituting hops which belong to virtual nodes and new sides in each path into the original topology information recoded in said topology structure.