| 摘要 |
<p>The present invention discloses a method and apparatus for implementing the K-shortest paths algorithm in the case of existing multiple edges between adjacent nodes. The method includes the following steps: recording original topological information into a topological structure; in order to divide each original edge except the original edge with the shortest weight into two new edges, adding a pseudo node on each original edge except the edge with the shortest weight, and obtaining the weights of the new edges by splitting the weight of the original edge which the new edges belong to; according to the new topological information after adding the pseudo node, computing K-shortest paths between appointed nodes; checking each path of the computed K-shortest paths in turn, reverting the hops belonging to the pseudo node and new edges on each path to the original topological information recorded in the topological structure. Applying the method, each edge can be involved in the computation of the K-shortest paths algorithm, instead of being shielded simply. Therefore, the result of the K-shortest algorithm can be accurate and reliable, and the actual K-shortest paths in topology can be computed.</p> |
