# GraphSAGE-Based Multi-Path Reliable Routing Algorithm for Wireless Mesh Networks
## 3 Multi-Path Routing Algorithm Based on the Improved Breadth First Search
### Breadth-First Search  
According to the collected network topology information, the connectivity between nodes in the network is represented by an adjacency matrix \(A(a_{ij})\), where the elements \(a_{ij}\) are defined as  
\[a_{ij}=\left\{\begin{array}{l}1,\;if\;\;node\;i\;\;and\;\;node\;j\;\;are\; connected\\ 0,\;else\end{array}\right. \tag{1}\]  
The breadth-first search uses an adjacency matrix \(A\) to traverse the information of neighbor nodes of the head node and calculate the shortest hop count and predecessor nodes from the neighbor node to the source. After all the neighbor nodes are traversed, the head node is out of the queue and a new head node is generated until the queue is empty. In this way, the shortest hop count of all nodes to the source and the predecessor nodes of each node are obtained. The flow chart of the improved breadth-first search is shown in Figure 3, and the specific steps are as follows.  
Figure 3: Flow chart of the improved breadth-first search.  
* First initialize the correlation parameters, put the source \(src\) as the head node \(Head\) into \(Queue\), set the status \(Visited\) of the source to \(True\), the rest of the nodes to \(False\), and the status \(Searched\) of all nodes to \(False\). Set \(HopCount(Head)\) to zero, which represents the hop count from the head node to the source is zero. Traverse adjacency matrix \(A\) to find all the neighbor nodes of the head node and the address of one of the neighbor nodes is denoted by \(Neighbor\). Query the current status of this neighbor node.
* If \(Visited=False\), \(HopCount(Neighbor)=HopCount(Head)+1\), and the number of predecessor nodes of this neighbor node \(FrontCount(Neighbor)\) is increased by one. At the same time, put the head node as the predecessor node of the current neighbor node into \(FrontPoint(Neighbor)\). Finally, put the neighbor node in \(Queue\) and set the status \(Visited\) of this node to \(True\).
* If \(Visited=True\), this node is also a neighbor node of other nodes, it is necessary to compare the size of the shortest hop count from the neighbor node to the source. If the shortest hop count obtained in this loop is smaller than the original one, update \(HopCount(Neighbor)\) to the shortest hop count of this loop and keep \(FrontCount(Neighbor)\) unchanged. If the shortest hop count obtained in this loop is equal to the original one, \(FrontCount(Neighbor)\) is increased by one. At the same time, put \(Head\) as another predecessor node of the current neighbor node into \(FrontPoint(Neighbor)\). If the shortest hop count obtained in this loop is larger than the original one, skip out of this loop.
* If \(Searched=True\), this node has been searched, so skip out of this loop. After all neighbor nodes are traversed, update the status \(Searched\) of the head node as \(True\). In the end, remove the head node from \(Queue\) and generate a new head node.
* Repeat steps 2 to 4 until \(Queue\) becomes empty.  
The shortest hop count from the source to each node and the predecessor nodes of each node have been obtained after a breadth-first search. Section 3.2 will use the information to output multipath.