# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 3 Shortest Paths
### Complexity Analysis  
We may associate a label \((eid,st,h)\) with each path \(p\in P(v,k)\), \(v\
eq s\), and \(k>0\), where \(eid\) is the id of the last edge, \((u,w)\), in \(p\) with a departure time that is the start, \(st\), of some travel interval of \((u,w)\) and \(h\) is the number of hops in the path \(p\) from \(s\) to \(u\). Note that every \(p\in P(v,k)\) has such a \((u,w)\) as the departure time for the first edge \((s,x)\) of \(p\) is the start of some interval of \((s,x)\) and the number of edges in \(p\) is finite. Let \(p_{l}\) be the portion of \(p\) from \(s\) to \(u\) and \(p_{r}\) that from \(u\) to \(v\) (see Figure 7). From the way our algorithm works, it follows that \(p_{l}\) is an \(h\)-hop path in \(P(u,h)\). Further, since the departure time for no edge in \(p_{r}\) is a start time of a travel interval for that edge (except \(st\) on \((u,w)\)), \(p_{r}\) encounters no wait at intermediate vertices and the length, \(len(p_{r})\), (i.e., sum of the edge travel times) of \(p_{r}\) is the same as its duration (arrival time at \(v\) - departure time from \(u\)). **Theorem 2**: _No \(P(v,k)\) has two paths with the same label._  
Assume there is a \(P(v,k)\) that has two paths \(p1\) and \(p2\) with the same label \((eid,st,h)\). We shall show that this assumption leads to a contradiction and so must be false. Note that \(p1\) and \(p2\) are pairwise non-dominant. 1. Case \(h=0\). Now, \(p1_{l}\) and \(p2_{l}\) are empty. Thus, \(len(p1)=len(p1_{r})=arr(p1)-st\) and \(len(p2)=arr(p2)-st\). When \(len(p1)<len(p2)\), we have \(arr(p1)<arr(p2)\). Thus, \(p1\) dominates \(p2\), which contradicts the fact that \(p1\) and \(p2\) are pairwise non-dominant. A contradiction is similarly obtained for the cases \(len(p1)=len(p2)\) and \(len(p1)>len(p2)\). 2. Case \(h>0\). Now, \(p1_{l}\) and \(p2_{l}\) are \(h\)-hop paths from \(s\) to the same vertex \(u\). The first edge of \(p1_{r}\) and \(p2_{r}\) is \((u,w)\) and both these paths start from \(u\) at time \(st\). Thus, \[arr(p1) =st+len(p1_{r})\] (4) \[arr(p2) =st+len(p2_{r})\] (5) \[len(p1) =len(p1_{l})+len(p1_{r})\] (6) \[len(p2) =len(p2_{l})+len(p2_{r})\] (7) (a) Case \(len(p1_{1})=len(p2_{l})\). Now, \(p1_{l}\) and \(p2_{l}\) must be the same path as, otherwise, one dominates the other, which is not possible as both are in \(P(u,r)\). If \(arr(p1)<arr(p2)\), then \(len(p1_{r})<len(p2_{r})\) (Equations (4) and (5)). Thus, \(len(p1)<len(p2_{r})\) (Equations (6) and (7)). Hence, \(p1\) dominates \(p2\), a contradiction. A similar proof shows that when \(arr(p1)>arr(p2)\), we obtain the contradiction that \(p2\) dominates \(p1\). 2. Case \(len(p1_{l})<len(p2_{l})\). Let \(p3\) be the \(s\) to \(v\) path obtained by concatenating \(p1_{l}\) and \(p2_{r}\). Note that \(p3\) is a \(k\)-hop time-respecting path with \(arr(p3)=arr(p2)\) and \(len(p3)=len(p1_{l})+len(p2_{r})<len(p2)\) (Equation (7)). Hence, \(p3\) dominates \(p2\). Thus, either \(p3\) or a path \(p4\) that dominates both \(p2\) and \(p3\) must be in \(P(v,k)\). This means that \(p2\) cannot be in \(P(v,k)\). 3. Case \(len(p1_{l})>len(p2_{l})\). This is similar to the previous case. No \(P_{new}(v,k)\) has two paths with the same label. Proof. : This is similar to that of Theorem 2. The number of distinct path labels \((\mathit{eid},st,h)\) is at most \(i*n\), where \(i\) is the total number of travel intervals across all edges of the temporal graph. From Theorems 2 and 3, it follows that \(|P(v,k)|\leq in\) and \(|P_{new}(v,k)|\leq in\) for all \(v\) and \(k\). For each value of \(k\), \(k>0\), the at most \(in\) paths in \(P_{new}(u,k-1)\) are considered in increasing order of length (equivalently, decreasing order of arrival time at \(u\)) and extended by one hop using an out edge from \(u\). When extending using the edge \((u,v)\) for each of these up to \(in\) paths, a binary search is performed over the travel intervals of this edge to determine the first interval for a valid extension (line 12 of Algorithm 2).