Method and apparatus for implementing K-shortest paths algorithm in the case of existing multiple edges between adjacent nodes

摘要

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.