# An Effective Algorithm for Finding Shortest Paths in Tubular Spaces
## 3 Basics of [PERSON]'s Algorithm  
The concept of this method, based on the lemma about the relationship between the global minimum and local minimum, was first presented by [PERSON] in 1959 (see [32], Problem 2). Despite also being based on Lemma 1, if applied to the directed graph, Algorithm 1 has a run time in \(O(|A|)\) instead of \(O(|V|log|V|+|A|)\), as is the case for the conventional [PERSON]'s algorithm used for a weighted graph [1]. In the literature, the \(A^{*}\) algorithm [36] is a good method for searching the shortest path in a weighted graph as it improves the calculation speed of [PERSON]'s algorithm for many cases. However, choosing an effective admissible heuristic function for this algorithm based on the geometry of the tubular space is beyond the scope of this paper. In addition, the complexity \(O(|A|)\) is already a good run time for this problem, so we do not consider the \(A^{*}\) algorithm in this work. Lemma 1 ([PERSON] algorithm, 1959): _\"If \(\mathbf{r}\) is a node on the minimal path from \(\mathbf{p}\) to \(\mathbf{q}\), the knowledge of the latter implies the knowledge of the minimal path from \(\mathbf{p}\) to \(\mathbf{r}\)\"._  
This lemma can easily be proven by contradiction. The shortest path from the source \(\mathbf{\mathfrak{P}}\) to the destination \(\mathbf{\Omega}\) will be traced by extending all extendable paths by one edge to a node not yet visited on this path until \(\mathbf{\Omega}\) is reached. Consequently, extending all the extendable paths from the source by one arc in the directed graph starts to turn the examined disk into its adjacent disk towards the destination. Upon examining a disk, the shortest path between the source and every node on the previous disks has been identified, so we do not need to revisit these points. Set \(\mathbf{r}_{i[i][j]}(i\in\{1,\ldots,N\},j\in\{1,\ldots,M\})\) as the node \(j\)th on the meshed disk \(S_{i}\). In addition, we denote \(D(\mathbf{x})\) as the minimum length from node \(\mathbf{\mathfrak{P}}\) to node \(\mathbf{x}\), \(\mathrm{w}(\mathbf{x},\mathbf{y})\) as the length of the arc connecting two adjacent nodes \(\mathbf{x}\) and \(\mathbf{y}\), and \(\mathcal{L}_{i[i][j]}\) as the list of nodes  
Figure 2: Discrete approach for the ESP problem. (**Left**) Inner space of the tube transformed into a series of meshed circular disks; and (**Right**) the directed graph. on the shortest path from source \(\mathfrak{P}\) to node \(\textbf{r}_{[i][j]}\) (for node \(\boldsymbol{\Omega}\), we utilize \(\mathcal{L}_{[\boldsymbol{\Omega}]}\)). We obtain [PERSON]'s algorithm applied for this ESP problem as given in Algorithm 1. ```
Input:\(\mathfrak{P},\boldsymbol{\Omega}\), and \(\textbf{r}_{[i][j]},\forall i\in\{1,\ldots,N\},\forall j\in\{1,\ldots,M\}\). Output:\(\mathcal{L}_{[\boldsymbol{\Omega}]}\). // Initialisation
1\(D(\boldsymbol{\Omega})\leftarrow+\infty\), \(D(\textbf{r}_{[i][j]})\leftarrow+\infty\), \(\forall i\in\{1,\ldots,N\},\forall j\in\{1,\ldots,M\}\); // From the source to \(S_{1}\) for\(j\gets 1\)to\(M\)do \(D(\textbf{r}_{[i][j]})\leftarrow\text{w}(\mathfrak{P},\textbf{r}_{[1][j]})\); \(\mathcal{L}_{[1][j]}\leftarrow\{\mathfrak{P},\textbf{r}_{[1][j]}\}\);
2
3 end for // Between \(S_{1}\) and \(S_{N}\) for\(i=2\)to\(N\)do for\(j=1\)to\(M\)do \(D(\textbf{r}_{[i][j]})\leftarrow min\{D(\textbf{r}_{[i][j]}),D(\textbf{r}_{[i-1][ k]})+\text{w}(\textbf{r}_{[i-1][k]},\textbf{r}_{[i][j]})\}\) If \(D(\textbf{r}_{[i][j]})\) is replaced, put a label \(K^{*}\gets k\). 4
5 end for \(\mathcal{L}_{[i][j]}\leftarrow\left[\mathcal{L}_{[i-1][K^{*}]},\textbf{r}^{ \prime}[i][j]\right]\) ; // add \(\textbf{r}_{[i][j]}\) to the list \(\mathcal{L}_{[i-1][K^{*}]}\)
6
7 end for // From \(S_{N}\) to the destination for\(k=1\)to\(M\)do \(D(\boldsymbol{\Omega})\gets min\{D(\boldsymbol{\Omega}),D(\textbf{r}_{[N ][k]})+\text{w}(\textbf{r}_{[N][k]},\boldsymbol{\Omega})\}\). // If \(D(\boldsymbol{\Omega})\) is replaced, put a label \(K^{*}\gets k\).