# Foremost Walks and Paths in Interval Temporal Graphs +
## 4 Min-Hop Foremost Paths
### Algorithm to Find mhf Paths in Interval-Temporal Graphs
#### 4.1.2 Algorithm Description  
* 1. Temporal graph represented by data structure described in Section 4.1.1, item 1 2. Source vertex \(s\)  
* - Array \(t_{EKA}\) as described in Section 4.1.1, item 4  
As an example, consider the interval-temporal graph of Figure 8. Let the source vertex be \(S\) and \(t_{start}=0\). In the first round (\(hopCnt=1\)), the neighbors \(A\), \(B\), and \(C\) are identified as one-hop neighbors of \(S\) with one-hop path arrival times of 1, 5, and 10, respectively. Therefore, the earliest known arrival time to these neighbors are updated with \(t_{EKA}\), with a \(hopCnt\) of 1. In the next round (\(hopCnt=2\)), these one-hop paths are expanded to two-hop paths to vertices \(B\) (\(S\), \(A\), \(B\) ) and \(C\) (\(S\), \(B\), \(C\)). The arrival times of these paths are 2 and 6, which is earlier than their current arrival times. Therefore, their earliest known arrival times (_foremost_ arrival times) are updated. In the third round (\(hopCnt=3\)), the earlier arriving 2-hop paths to \(B\) and \(C\) are expanded. While the 2-hop path to \(C\) cannot be expanded any further, the 2-hop path to \(B\) is expanded to obtsin a 3-hop path to \(C\) that gets to \(C\) at 4, which is earlier than its current arrival time. Therefore, \(t_{EKA}\) is again updated for this vertex. This path is expanded in the next round (\(hopCnt=4\)) and the 4-hop path to \(D\) (\(S\), \(A\), \(B\), \(C\), \(D\)) is discovered, which is also the \(foremost\) arrival time at \(D\). This path arrives at \(D\) at 5. The algorithm now terminates as \(hopCnt=4=V-1\).  
Figure 8: \(mhf\) paths in interval-temporal graphs.  
```
1:Create \(startSt\leftarrow(s,t_{start},null)\) as an instance of \(incSt\).
2:Initialize \(t_{EKA}[s]\gets t_{start};\forall v\in V,v\
eq s,t_{EKA}[v]\leftarrow\infty\); Initialize \(allHopPaths[0]\leftarrow\{startSt\}\)
3:\(hopCnt=0;newVsInHop=1;totVsRchd=1\)
4:while\((hopCnt<V-1)\) and \((newVsInHop\geq 0)\)do
5:\(hopCnt++\)
6:\(newVsInHop\gets 0\)
7:for each\((refIncSt\in alHopPhhs[hopCnt-1])\)do
8:\(vert=refIncSt.curVtxId\)
9:\(t_{vertArr}=refIncSt.arrTm\)
10:for each\((hbr\in V[vert].nbrs)\)do
11:\((depTm,intvId)=f((vert,nbr),t_{vertArr})\)
12:if\(depTm\geq\infty\)then
13:continue\(\triangleright\) start next loop iteration
14:endif
15:\(newAr_{nbr}=depTm+\lambda_{intvId}\)
16:if\((newAr_{nbr}<t_{EKA}[nbr].t_{f})\)then
17:if\((hopCnt>t_{EKA}[nbr].h_{f})\)then
18: Create an instance of \(incStruct\) as \(nis\leftarrow(nbr,newAr_{nbr},refIncSt)\)
19:\(t_{EKA}[nbr].h_{f}=hopCnt\)
20:\(alHopPths[hopCnt].append(nis)\)
21:\(t_{EKA}[nbr].indx=newVsInHop++\)
22:else\(\triangleright\) arrival with an earlier time in same hop from a diferent prev node
23: Update
24:\(alHopPths[hopCnt][t_{EKA}[nbr].indx]\)
25:endif
26:if\(t_{EKA}[nbr].t_{f}\geq\infty\)then
27:\(totVsRchd++\)
28:endif
29:\(t_{EKA}[nbr].t_{f}=newAr_{nbr}\)
30:endif
31:endfor
32:endfor
33:endfor
34:endwhile
```  
**Algorithm 1** Min-hop foremost path algorithm  
Theorem 7: Algorithm 1 finds \(mhf\) paths from the source vertex, \(s\), to all reachable vertices \(v\in V\) in the interval-temporal graph \(G=(V,E)\)  
Proof: The proof follows from Theorem 6 and the observation that the algorithm constructs \(mhf\) paths first with 1 hop, then with 2 hops, and so on. Form Theorem 6, it follows that, on each round, it is sufficient to examine only 1-hop extensions of paths constructed in the previous round.  
The asymptotic complexity of Algorithm 1 is \(O(NM_{ig}\log\delta)\), where \(N\) and \(M_{ig}\) are the number of vertices and edges, respectively, in the interval temporal graph and \(\delta\) is the maximum number of departure intervals on an edge from the given \(M_{ig}\) edges. This is the same as that of the min-hop algorithm in our earlier paper [13].