# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 1 Introduction
[17] developed a polynomial time algorithm, for \(CSG\)s, to compute walks that optimize any linear combination of the optimization criteria studied by [15; 16; 18; 20] with min and max waiting time constraints at each vertex. [PERSON] et al. [19] show that a linear combination of multiple criteria can be used to find walks and paths with a secondary optimization criterion for, e.g., min-hop foremost (\(mhf\)) paths or min-wait foremost (\(mvf\)) walks. [PERSON] et al. [19] present algorithms for dual criteria \(min-hop-foremost\) (\(mhf\)) and \(min-wait-foremost\) (\(mvf\)) for \(IT\)Gs. Their ITG algorithms solve the \(mhf\) and \(mvf\) problems in less time than when the algorithm of [PERSON] et al. [17] is used on the corresponding CSGs and the coefficients of the linear combination optimization criteria in [PERSON] et al. 's algorithm are chosen so as to compute \(mhf\) and \(mvf\) walks. [PERSON] et al. [21] also develop an algorithm to compute walks optimizing any linear combination of the criteria considered by [PERSON] et al. [17] with waiting time constraints, outperforming the algorithm by [PERSON] et al. by up to a factor of 77. However, the limitation of the algorithm by [PERSON] et al. is that it only works on \(CSG\)s with no zero-duration cycle. In this paper, we develop an algorithm to find the shortest paths in \(IT\)Gs. A shortest path between any two vertices \(A\) and \(B\) in a temporal graph is a feasible path for which the travel time to reach from \(A\) to \(B\) is minimum. [PERSON] et al. [16] propose a polynomial time algorithm to find min-hop paths in \(IT\)Gs. A min-hop path from vertex \(A\) to \(B\) is a feasible path that travels through the minimum number of edges to reach \(B\). Such a path is also the shortest path from \(A\) to \(B\) when all edges have the same travel time. However, in general, travel times on the edges of an interval temporal graph may be different. No algorithm has been proposed for finding the shortest paths when the temporal graph is expressed as an \(ITG\). [PERSON] et al. [15], [PERSON] et al. [17], [PERSON] et al. [21] and others proposed algorithms that can be used to find the shortest paths when temporal graphs are expressed as \(CSG\)s. As noted earlier, \(IT\)Gs cannot be expressed as \(CSG\)s when time is continuous. Further, even when time is discrete, the size of the \(CSG\) corresponding to a given \(ITG\) could be quite large (when the time intervals of edges are large). This paper fills this gap by providing a polynomial time shortest path algorithm for \(ITG\)s.  
Experimentally, it is demonstrated that as the contiguous time intervals that allow travel on edges in temporal graphs become larger, our \(ITG\) shortest path algorithm shows increasing performance gains over the algorithm by [PERSON] et al. [15] running on the same temporal graph expressed as a \(CSG\). Our main contributions are as follows:  
1. We develop a polynomial time algorithm to find the shortest paths in an \(ITG\). To the best of our knowledge, no such algorithm is presently available in the literature. 2. We provide the complexity analysis of our shortest path algorithm. 3. We benchmark our algorithm for \(ITG\)s against that of [PERSON] et al. [15] for finding the shortest paths in \(CSG\)s. Experimentally, we show that as the activity factor in a temporal graph increases due to large contiguous travel intervals, our algorithm shows increasing performance gains over that of [PERSON] et al. [15] on equivalent temporal graphs expressed as \(CSG\)s. Using synthetic datasets, we show that our algorithm for \(ITG\)s obtains a speedup of up to 32.5 relative to the state-of-the-art algorithm for \(CSG\)s.