## 6 Material and Method
### Single Source Shortest Path Algorithm  
The SSSP algorithm calculates the shortest path between a starting node and every other node in the graph. This means that to calculate the shortest path between a DP and every other DP, the SSSP only needs to be run once. It also means that to calculate the shortest paths linking any two DPs in a set of \(N\) DPs, \(N\) instances of the SSSP algorithm need to be run. Depending on the weights assigned to the edges of the graph, the final path may minimize distance, time, or energy. In the proposed framework, two implementations of the SSSP algorithm are used. The first one is the Dijkstra algorithm provided by the C++ Boost library [27]. This implementation is regarded as highly efficient and is used here as the reference for the sequential program. The second implementation is an improved version developed by the author of this paper of the parallel SSSP algorithm proposed by [PERSON] et al. [28] for the GPU architecture. As it was shown in a previous publication [29], this adaptation is more performant than other implementations on GPU recently published in the literature [30; 31]. This second implementation is preferred due to its shorter execution time which allows for recalculation of the paths in case new obstacles or new sensors are discovered. The details of [PERSON] et al. 's algorithm are presented at Algorithms 3-5. Algorithms 3 and 5 are from the original algorithm developed by [PERSON] et al. while Algorithm 4 is the improved version proposed in this paper. The SSSP algorithm keeps an array of frontier flags \(F\), of cost \(C\) and of updated cost \(U\) of size \(n\) where \(n\) is the number of nodes in the graph. The array \(F\) identifies the nodes whose weights have been updated in an iteration and that must be visited in the next iteration. These nodes are said to be at the frontier. The array \(C\) keeps the cost of the node, i.e., the cost needed to travel from the start node to the node. The array \(U\) is used to update the nodes cost synchronously at each iteration. Initially, the \(F\) array is set to false, the \(C\) array and the \(U\) array are set to infinity. At line 2 of Algorithm 3, the flag for the start node is set to true and its cost and updated cost are set to 0. A sum value which represents the number of nodes at the frontier is set to 1. The algorithm then goes into a while loop for as long as there are nodes in the frontier. The loop is composed of two kernels (parallel functions in CUDA). In the first kernel, all the nodes are visited in parallel using one thread per node. Nodes that are at the frontier have the weight of their neighbors updated as needed. This update operation creates a race condition as multiple threads could be updating the same node. In the original algorithm, an atomic operation was used by [PERSON] et al. (2018), but this operation slowed down the execution of the algorithm. In the proposed implementation, the atomic operation is avoided by forcing the source node _tid_ to remain in the frontier node so that it is revisited at the next iteration. This means that if the value it wrote to \(U[i]\) was overwritten by another thread, it would rewrite the value to \(U[i]\) at the next iteration. This necessarily generates more iterations, but avoids the atomic operation. Overall, a faster execution was observed by avoiding the atomic operation. In the second kernel, all nodes are visited and any nodes whose cost was updated have their flag set to true. These nodes are now part of the frontier and will be visited at the next iteration. After kernel 2 finishes, a parallel reduction is used to calculate the number of nodes in the frontier and the algorithm proceeds to the next iteration of the while loop. After the SSSP algorithm terminates, the cost array is transferred from the GPU to the CPU. The cost arrays for all instances of the SSSP are kept in memory for the path reconstruction phase explained in Section 6.6.