Shortest path search method “Midway”
First Claim
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.
0 Assignments
0 Petitions
Accused Products
Abstract
A method of searching for a shortest path from a single source node to a single destination node in a two dimensional computer network. The method is similar to Dijkstra shortest path algorithm (“Dijkstra”) in the way it builds a shortest path tree. However, instead of starting from the source node and searching through to the destination node as Dijkstra does, the method runs a shortest path search from both ends (i.e. source and destination) simultaneously or alternatively, until a shortest path tree from one end meets a shortest path tree from the other end at an intermediate node, and the concatenated path (source node intermediate node-destination node) satisfies a condition. Conditions other than those used by Dijkstra determine when the search should terminate, and whether the search has succeeded or failed. It has been verified that the new method requires less overhead and time than Dijkstra.
69 Citations
28 Claims
-
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, and if 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, and the 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.
-
-
2. A method of performing a shortest path search from a single source node to a single destination node in a two dimensional computer network, wherein the method takes advantage of the power of parallel processing provided by multi-threading or multi-tasking in a multi-processor environment to perform the shortest path search from both the source node and destination node simultaneously, the method, based on multithreaded programming compliant to a POSIX standard, comprising:
-
using a Boss-Worker parallel programming model comprising; two worker threads comprising a forward worker thread for running a forward shortest path search function for building a forward shortest path tree and a backward worker thread for running a backward shortest path search function for building a backward shortest path tree, wherein the forward worker thread runs the forward shortest path search function on a first processor, the backward worker thread runs the backward shortest path search function on a second processor, and the first and second processors run in parallel, and a boss thread for running a shortest path search management function, the boss thread being created by a main thread of a routing process, wherein the boss thread creates and initializes global variables and data structures required by the two worker threads to run the forward shortest path search function and backward shortest path search function, a portion of the data structures are shared by the two worker threads, the boss thread creates mutexes or read write locks to synchronize concurrent access to the portion of the data structures shared by the two worker threads, the boss thread creates condition predicates, condition variables and their associated mutexes to coordinate synchronization between the boss thread and the two worker threads, the boss thread uses one set of condition predicates and condition variables to wake up one of the two worker threads while the worker thread is waiting for a shortest path search job, each of the two worker threads uses another set of condition predicates and condition variables to wake up the boss thread while it is waiting for the shortest path search job to be done, and the boss thread creates a communication means for the two worker threads to communicate with each other; maintaining the two worker threads in a wait state wherein the two worker threads wait for the shortest path search job, when the boss thread identifies a need to find a shortest path through the network, the boss thread wakes up each of the two worker threads by signaling its condition variable, so the forward worker thread will start to run the forward shortest path search function to build the forward shortest path tree from the source node and the backward worker thread will start to run the backward shortest path search function to build the backward shortest path tree from the destination node simultaneously wherein a thread scheduling policy allows the forward worker thread to run the forward shortest path search function as soon as the forward worker thread is awoken by the boss thread, and the thread scheduling policy will not preempt the forward worker thread until the shortest path search job is completed, and the thread scheduling policy allows the backward worker thread to run the backward shortest path search function as soon as the backward worker thread is awoken by the boss thread, and the thread scheduling policy will not preempt the backward worker thread until the shortest path search job is completed; maintaining the boss thread in a wait state to wait for the shortest path search to be done; and after one of the two worker threads has a result comprising successfully finding a shortest path or determining the shortest path search has failed, the worker thread stops searching, notifies the other worker thread to stop searching, and wakes up the boss thread to process the result of shortest path search.
-
-
3. A method of terminating a shortest path search for a shortest path and determining whether the shortest path search for the shortest path succeeded or failed, the shortest path comprising a path extending through a two dimensional computer network comprising a plurality of nodes, the path extending from a single source node to a single destination node, wherein the shortest path search searches for the shortest path from the single source node and single destination node alternately or simultaneously, and the shortest path search comprises one of a minimum hop path search and a minimum cost path search,
if the shortest path search comprises the minimum hop path search, the minimum hop path search comprises constructing a forward minimum hop path tree having a plurality of leave nodes and a root node, the root node comprising the source node and constructing a backward minimum hop path tree having a plurality of leave nodes and a root node, the root node comprising the destination node, if the shortest path search comprises the minimum cost path search, the minimum cost path search comprises: -
constructing a forward 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; constructing a backward 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; for the forward minimum cost path tree, constructing a corresponding leave node list comprising the plurality of leave nodes of the forward minimum cost path tree; for the backward minimum cost path tree, constructing a corresponding leave node list comprising the plurality of leave nodes of the backward minimum cost path tree; identifying a current search direction tree comprising one of the forward minimum cost path tree and backward minimum cost path tree; identifying an opposite search direction tree comprising the other of the forward minimum cost path tree and backward minimum cost path tree; the minimum cost path search determines the minimum cost path search has succeeded when; a 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, and the 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 paths, 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 Dependent Claims (4, 5, 6)
-
-
7. A method of determining a minimum cost path extending from a source node of a plurality of nodes to a destination node of the plurality of nodes, wherein each node of the plurality of nodes is linked to another node of the plurality of nodes by a link having a link cost, and the minimum cost path extends from the source node to the destination node over the links connecting the nodes, the method comprising:
-
creating a forward leave node list comprising the source node; creating a backward leave node list comprising the destination node; creating a forward search tree comprising a root node having a current node path cost and setting the root node equal to the source node; creating a backward search tree comprising a root node having a current node path cost and setting the root node equal to the destination node; initializing a candidate minimum cost path cost by setting the candidate minimum cost path cost equal to a predetermined value; initializing a candidate minimum cost path; selecting one of the forward leave node list and backward leave node list as the selected list, the other of the forward leave node list and backward leave node list being an unselected list; selecting a searching node from the selected list; until a termination condition is satisfied; i. if the selected list is the forward leave node list, the selected search tree is the forward search tree and the unselected search tree is the backward search tree, otherwise, the selected tree is the backward search tree and the unselected search tree is the forward search tree; ii. for each node of the plurality of nodes linked to the searching node, a. selecting the node as the searched node; b. determining whether the searched node is linked to the selected search tree; c. if the searched node is not linked to the selected search tree, linking the searched node to the selected search tree with a tree link linking the searched node to the searching node, and assigning a current node path cost to the searched node, the current node path cost being equal to the sum of the current node path cost of the searching node and the link cost between the searched node and searching node; d. if the searched node is linked to the selected search tree and the searched node is not located on a path connecting the root node and the searching node, determining a node path cost for the searched node by summing the current node path cost of the searching node and the link cost between the searching node and searched node, and comparing the node path cost with the current node path cost of the searched node, if the node path cost is less than the current node path cost of the searched node removing the tree link connecting the searched node to the selected tree, linking the searched node to the searching node on the selected search tree with a tree link, and setting the current node path cost of the searched node equal to the node path cost; and e. searching the unselected search tree to determine whether the searched node is linked to the unselected search tree, if the searched node is linked to the unselected search tree, determine a concatenated path cost by adding the current node path cost of the searched node in the selected search tree to the current node path cost of the searched node in the unselected search tree, and compare the concatenated path cost to the candidate minimum cost path cost, if the concatenated path cost is less than the candidate minimum cost path cost, set the candidate minimum cost path cost equal to the concatenated path cost and set the candidate minimum cost path equal to a concatenated path comprising a path from the root node of the selected search tree to the searched node and a path from the root node of the unselected search tree to the searched node; f. adding the searched node to the selected list; iii. removing the searching node from the selected list; iv. if the selected list is the forward leave node list, select the backward leave node list as the selected list and the forward leave node list as the unselected list, otherwise, select the forward leave node list as the selected list and the backward leave node list as the unselected list; and v. if the selected list includes at least one node, selecting the searching node from the selected list, otherwise determining the termination condition is satisfied; and determining the minimum cost path is the candidate minimum cost path or the minimum cost path does not exist. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A method of determining a minimum hop path extending from a source node of a plurality of nodes to a destination node of the plurality of nodes, wherein each node of the plurality of nodes is linked to at least one other node of the plurality of nodes by a link, and the minimum hop path extends from the source node to the destination node over the links connecting the nodes of the plurality of nodes, the method comprising:
-
creating a forward searching node list comprising the source node; creating a forward searched node list; creating a backward searching node list comprising the destination node; creating a backward searched node list; creating a forward search tree comprising a root node and setting the root node equal to the source node; creating a backward search tree comprising a root node and setting the root node equal to the destination node; selecting one of the forward searching node list and backward searching node list as the selected list, the other of the forward searching node list and backward searching node list being an unselected list; selecting a searching node from the selected list; until a termination condition is satisfied; a. if the selected list is the forward searching node list, the selected search tree is the forward search tree and the unselected search tree is the backward search tree, otherwise, the selected search tree is the backward search tree and the unselected search tree is the forward search tree; b. if the selected list is the forward searching node list, the selected searched node list is the forward searched node list and the unselected searched node list is the backward searched node list, otherwise, the selected searched node list is the backward searched node list and the unselected searched node list is the forward searched node list; c. for each node of the selected list, select a searching node from the selected searching node list, i. for each node of the plurality of nodes linked to the searching node, selecting the node as the searched node; and if the searched node is not linked to the selected search tree, linking the searched node to the selected search tree with a tree link by linking the searched node to the searching node with the tree link; and
searching the unselected search tree to determine whether the searched node is linked to the unselected search tree,if the searched node is linked to the unselected search tree, identifying a minimum hop path comprising a path from the root node of the selected search tree to the searched node and a path from the root node of the unselected search tree to the searched node, and determining the termination condition is satisfied, otherwise, adding the searched node to the selected searched node list, and ii. removing the searching node from the selected list; d. swapping the nodes of the selected list and the selected searched node list; e. if the selected searched node list is the forward searched node list, select the backward searching node list as the selected list and the forward searching node list as the unselected list, otherwise, select the forward searching node list as the selected list and the backward searching node list as the unselected list; and f. if the selected list includes at least one node, selecting the searching node from the selected list, otherwise determining the termination condition is satisfied. - View Dependent Claims (13)
-
-
14. A method of determining a minimum cost path extending from a source node of a plurality of nodes to a destination node of the plurality of nodes, wherein each node of the plurality of nodes is linked to at least one other node of the plurality of nodes by a link having a link cost, and the minimum cost path extends from the source node to the destination node over the links connecting the nodes, the method comprising:
-
creating a forward leave node list comprising the source node; creating a backward leave node list comprising the destination node; creating a forward search tree comprising a root node having a current node path cost and setting the root node equal to the source node; creating a backward search tree comprising a root node having a current node path cost and setting the root node equal to the destination node; initializing a candidate minimum cost path cost by setting the candidate minimum cost path cost equal to a predetermined value; initializing a candidate minimum cost path; determining the minimum cost path is the candidate minimum cost path or the minimum cost path does not exist by conducting a forward search and a backward search until a termination condition is satisfied, wherein the forward search comprises; a. if the forward leave node list includes at least one node, selecting the forward searching node from the forward leave node list, otherwise determining the termination condition is satisfied; b. for each node of the plurality of nodes linked to the forward searching node, i. selecting the node as the forward searched node; ii. determining whether the forward searched node is linked to the forward search tree; iii. if the forward searched node is not linked to the forward search tree, linking the forward searched node to the forward search tree with a tree link linking the forward searched node to the forward searching node and assigning a current node path cost to the forward searched node, the current node path cost being equal to the sum of the current node path cost of the forward searching node and the link cost between the forward searched node and forward searching node; iv. if the forward searched node is linked to the forward search tree and the forward searched node is not located on a path connecting the root node and the forward searching node, determining a node path cost for the forward searched node by summing the current node path cost of the forward searching node and the link cost between the forward searching node and forward searched node, and comparing the node path cost with the current node path cost of the forward searched node, if the node path cost is less than the current node path cost, removing the tree link connecting the forward searched node to the forward search tree, linking the forward searched node to the forward searching node with a tree link, and setting the current node path cost of the forward searched node equal to the node path cost; v. searching the backward search tree to determine whether the forward searched node is linked to the backward search tree, if the forward searched node is linked to the backward search tree, determine a concatenated path cost by adding the current node path cost of the forward searched node in the forward search tree to the current node path cost of the forward searched node in the backward search tree, and compare the concatenated path cost to the candidate minimum cost path cost, if the concatenated path cost is less than the candidate minimum cost path cost, setting the candidate minimum cost path cost equal to the concatenated path cost and set the candidate minimum cost path equal to a concatenated path comprising a forward path from the root node of the forward search tree to the forward searched node and a backward path from the root node of the backward search tree to the forward searched node; and vi. adding the forward searched node to the forward leave node list; and c. removing the forward searching node from the forward leave node list; the backward search comprises; a. if the backward leave node list includes at least one node, selecting the backward searching node from the backward leave node list, otherwise determining the termination condition is satisfied; b. for each node of the plurality of nodes linked to the backward searching node, i. selecting the node as the backward searched node; ii. determining whether the backward searched node is linked to the backward search tree; iii. if the backward searched node is not linked to the backward search tree, linking the backward searched node to the backward search tree with a tree link linking the backward searched node to the backward searching node, and assigning a current node path cost to the backward searched node, the current node path cost being equal to the sum of the current node path cost of the forward searching node and the link cost between the backward searched node and backward searching node; iv. if the backward searched node is linked to the backward search tree and the backward searched node is not located on a path connecting the root node and the backward searching node, determining a node path cost for the backward searched node by summing the current node path cost of the backward searching node and the link cost between the backward searching node and backward searched node, and comparing the node path cost with the current node path cost of the backward searched node, if the node path cost is less than the current node path cost, removing the tree link connecting the backward searched node to the backward search tree, adding a tree link between the backward searching node and backward searched node, and setting the current node path cost of the backward searched node equal to the node path cost; V. searching the forward search tree to determine whether the backward searched node is linked to the forward search tree, if the backward searched node is linked to the forward search tree, determine a concatenated path cost by adding the current node path cost of the backward searched node in the backward search tree to the current node path cost of the backward searched node in the forward search tree, and compare the concatenated path cost to the candidate minimum cost path cost, if the concatenated path cost is less than the candidate minimum cost path cost, setting the candidate minimum cost path cost equal to the concatenated path cost and set the candidate minimum cost path equal to a concatenated path comprising a forward path from the root node of the forward search tree to the backward searched node and a backward path from the root node of the backward search tree to the backward searched node; and vi. adding the backward searched node to the backward leave node list; c. removing the backward searching node from the backward leave node list. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A method of determining a minimum hop path extending from a source node of a plurality of nodes to a destination node of the plurality of nodes, wherein each node of the plurality of nodes is linked to at least one other node of the plurality of nodes by a link, and the minimum hop path extends from the source node to the destination node over the links connecting the nodes of the plurality of nodes, the method comprising:
-
creating a forward searching node list comprising the source node; creating a forward searched node list; creating a backward searching node list comprising the destination node; creating a backward searched node list; creating a forward search tree comprising a root node and setting the root node equal to the source node; creating a backward search tree comprising a root node and setting the root node equal to the destination node; determining the minimum hop path is a concatenated path or the minimum hop path does not exist by conducting a forward search and a backward search until a termination condition is satisfied, wherein the forward search comprises; a. if the forward searching node list includes at least one node, selecting the forward searching node from the forward searching node list, otherwise determining the termination condition is satisfied; b. for each node of the forward searching node list, selecting a forward searching node by selecting the node from the forward searching node list, i. for each node of the plurality of nodes linked to the forward searching node, selecting a forward searched node by selecting the node, and if the forward searched node is not linked to the forward search tree, linking the forward searched node to the forward search tree with a tree link and searching the backward search tree to determine whether the forward searched node is linked to the backward search tree, if the forward searched node is linked to the backward search tree, determining the concatenated path by concatenating a forward path from the root node of the forward search tree to the forward searched node and a backward path from the root node of the backward search tree to the forward searched node, and determining the termination condition is satisfied, otherwise adding the forward searched node to the forward searched node list; and ii. removing the forward searching node from the forward searching node list; and c. swapping the nodes of the forward searching node list and the forward searched node list; and the backward search comprises; a. if the backward searching node list includes at least one node, selecting the backward searching node from the backward searching node list, otherwise determining the termination condition is satisfied; b. for each node of the backward searching node list, selecting a backward searching node by selecting the node from the backward searching node list, i. for each node of the plurality of nodes linked to the backward searching node, selecting a backward searched node by selecting the node, if the backward searched node is not linked to the backward search tree, linking the backward searched node to the backward search tree with a tree link and searching the forward search tree to determine whether the backward searched node is linked to the forward search tree, if the backward searched node is linked to the forward search tree, determining the concatenated path by concatenating a backward path from the root node of the backward search tree to the backward searched node and a forward path from the root node of the forward search tree to the backward searched node, and determining the termination condition is satisfied, otherwise adding the backward searched node to the backward searched node list; and ii. removing the backward searching node from the backward searching node list; and c. swapping the nodes of the backward searching node list and the backward searched node list. - View Dependent Claims (25, 26, 27, 28)
-
Specification