×

Shortest path search method “Midway”

  • US 7,280,481 B2
  • Filed: 10/10/2002
  • Issued: 10/09/2007
  • Est. Priority Date: 10/10/2002
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method to search for a shortest path through a two dimensional computer network comprising a plurality of nodes, wherein the shortest path extends from a single source node of the plurality of nodes to a single destination node of the plurality of nodes, the method comprising performing a shortest path search from both the single source and the single destination node alternatively using a single task and a single function in a single processor environment, wherein the shortest path search comprises one of a minimum hop path search and a minimum cost path search having a plurality of rounds, each round being executed by the single processor using code, the same code being executed by the single processor each round, wherein performing the shortest path search comprises:

  • declaring two identical sets of data structures, a forward set of data structures for searching from the source node and a backward set of data structures for searching from the destination node,if the shortest path search comprises the minimum hop path search, each set of data structures comprises a minimum hop path tree having a plurality of branches, a plurality of leave nodes and a root node, the root node of the minimum hop path tree of the forward set of data structures comprising the source node and the root node of the minimum hop path tree of the backward set of data structures comprising the destination node, andif the shortest path search comprises the minimum cost path search, each set of data structures comprises a minimum cost path tree comprising a plurality of branches each having a path cost and path hops, and a plurality of leave nodes comprising a least cost leave node having a plurality of neighbor nodes, the plurality of branches comprising a least cost branch having a least path cost and a number of least path hops, the least path cost being less than the path cost of the other branches of the plurality of branches, and the least cost leave node being located at an end of the least cost branch;

    declaring a set of pointers comprising a pointer to each data structure of one of the forward and backward sets of data structures;

    swapping pointers to one of the forward and backward sets of data structures to the other after each round of the plurality of rounds of the shortest path search, if the shortest path search comprises the minimum cost path search, the minimum cost path tree of the pointed to sets of data structures is the current search direction tree and the minimum cost path tree of the other sets of data structures is the opposite search direction tree;

    performing a round of the plurality of rounds of the shortest path search, until a certain condition is satisfied,if the shortest path search comprises the minimum hop path search, the round of the shortest path search comprises exhausting all leave nodes existing on the minimum hop path tree at the beginning of the round,if the shortest path search comprises the minimum cost path search, the round of shortest path search comprises exhausting all neighbor nodes of the least cost leave node of the current search direction tree, the method differing from Dijkstra'"'"'s algorithm by inserting the leave nodes into a sorted double linked leave node list having a head, the least cost leave node being at the head of the leave node list, so the least cost leave node is ready for use in the next round, and using the current search direction tree to identify a candidate shortest path or determine a shortest path does not exist,wherein the certain condition comprises determining the shortest path search has succeeded or failed,the minimum hop path search determines the minimum hop path search has succeeded when a minimum hop path is successfully found by determining a leave node of the minimum hop path tree of one of the forward and backward sets of data structures meets a leave node of the minimum hop path tree of the other of the forward and backward sets of data structures,the minimum hop path search determines the minimum hop search has failed when the source and destination nodes are not connected, the minimum hop search determines the source and destination nodes are not connected by determining all of the leave nodes of the minimum hop path tree of one of the forward and backward sets of data structures have been looked up and no path linking the source node and the destination node was found,the minimum cost path search determines the minimum cost path search has failed when the source node and destination node are not connected, determining the source node and destination node are not connected comprising determining the leave node list of the current search direction tree is exhausted and the candidate shortest path was not identified,the minimum cost path search determines the minimum cost path search has succeeded when;

    the candidate shortest path is identified, the candidate shortest path is identified when the least cost branch of the current search direction tree meets a leave node of the plurality of leave nodes of the opposite search direction tree, a concatenated path is identified, the concatenated path comprises the least cost branch of the current search direction tree and a branch of the opposite search direction tree comprising the leave node, and the candidate shortest path comprises the concatenated path if the concatenated path is the first one identified, if the concatenated path is not the first one identified, the candidate shortest path is replaced by the concatenated path if the concatenated path is less expensive than the candidate shortest path, andthe candidate shortest path is determined to be the shortest path, the candidate shortest path is determined to be the shortest path when the candidate shortest path is identified and the leave node list is exhausted or if the leave node list is not exhausted, the candidate shortest path is determined to be the shortest path when the candidate shortest path is not more expensive than a virtual minimum cost path, wherein determining which of the candidate shortest path and the virtual minimum cost path is more expensive comprises;

    calculating a total path cost of the virtual minimum cost path by adding the least path cost of the least cost branch of the current search direction tree and the least path cost of the least cost branch of the opposite search direction tree,calculating a number of total path hops of the virtual minimum cost path by adding the number of least path hops of the least cost branch of the current search direction tree and the number of least path hops of the least cost branch of the opposite search direction tree,calculating a candidate path cost and candidate path hops for the candidate shortest path,comparing the total path cost and the number of total path hops of the virtual minimum cost path with the candidate path cost and candidate path hops of the candidate shortest path; and

    determining the candidate shortest path is not more expensive than the virtual minimum cost path if the total path cost of the virtual minimum cost path is greater than the candidate path cost, or the total path cost of the virtual minimum cost path is equal to the candidate path cost and the number of total path hops of the virtual minimum cost path is greater than the candidate path hops.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×