# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 3 Shortest Paths
### Detailed Algorithm  
Algorithm 2 is a refinement of Algorithm 1 that provides a greater level of detail. The function \(next1((u,v),(t,l))\) (line 12 of Algorithm 2) finds the earliest possible departure time \(fstout\) and corresponding interval \(i_{F}\) on the edge \((u,v)\). If \(t\) is in the interval \((i_{F}.st,i_{F}.c)\), \(fstout\) is the same as \(t\), otherwise it is \(i_{F}.st\). The lists of paths \((t,l)\) arriving at a vertex are always kept in increasing order of \(t\). In a list of non-dominated paths, the increasing order of \(t\) is the same as the decreasing order of \(l\) due to the dominance criteria of Section 3.1. In line 17, \(ptrendDom(P^{\prime\prime}_{new}(v,k),(t^{\prime},l^{\prime}))\) prepends extended path \((t^{\prime},l^{\prime})\) to the list \(P^{\prime\prime}_{new}(v,k)\) since paths \((t,l)\) from the predecessor vertex \(u\) are extended in decreasing order of \(t\). After prepending \((t^{\prime},l^{\prime})\) to \(P^{\prime\prime}_{new}(v,k)\), \(ptrendDom\) eliminates any subsequent paths in the list that \((t^{\prime},l^{\prime})\) dominates. In lines 11 to 24, every \((t,l)\) is extended using an outgoing edge \((u,v)\) and the earliest possible departure time \(fstout\) (\(\geq t\)) from \(u\). Then, \((t,l)\) is also extended at \(i.st\) for every subsequent interval \(i\) on \((u,v)\), such that \(i.st<prev(fstout)\), where \(prev(fstout)\) is the extension time of a previously examined path \((t_{p},l_{p})\) at \(u\). This is because extension of \((t,l)\) would be dominated by the extension of \((t_{p},l_{p})\) if it starts at \(t_{x}\geq prev(fstout)\) with the same travel time \(\lambda_{x}\) since \(l_{p}<l\). In line 25, the list of extensions of all paths from \(u\) to \(v\) is merged with any other such list from a different incoming edge \((u^{\prime},v)\) in the current hop, retaining only non-dominated paths. The resulting \(P^{\prime}_{new}(v,k)\) is added to \(txtPLists\), which maintains all such lists obtained at every vertex \(v\) in hop \(k\). Figure 6: Shortest paths in \(ITG\) example. ```
1:Initialize \(P(v,0)\gets NULL\), \(\forall v\
eq s\); \(P(s,0)\leftarrow(0,0)\)
2:Initialize \(newPLists\) as empty list. \(P_{new}(s,0)\leftarrow(0,0)\). 3:\(\forall v\
eq s\), \(shtrstP[v]\leftarrow(\infty,\infty)\); \(shtrstP[s]\leftarrow(0,0)\)
4:Add \([s,P_{new}(s,0)]\) to \(newPLists\)
5:Initialize \(k\gets 0\); \(newPaths\gets 1\)
6:while\(k<n-1\) and \(newPaths>0\)do
7:\(newPaths\gets 0\);\(k++\)
8:for all\(u\) in \(newPLists\)do
9:for all neighbors \(v\) of \(u\)do
10: Initialize \(prevPath(fstout)\leftarrow\infty\)
11:for all\((t,l)\in P_{new}(u,k-1)\) in dec order of \(t\)do
12:\((i_{F},fstout)\gets nextl((u,v),(t,l))\)
13:if\(fstout\geq prevPath(fstout)\)then
14: continue
15:endif
16:\((t^{\prime},l^{\prime})\leftarrow(fstout+i_{F}.\lambda,l+i_{F}.\lambda)\)
17:\(\text{prpendDom}(P^{\prime\prime}_{new}(v,k),(t^{\prime},l^{\prime}))\)
18:for\((\{i_{x}\in(u,v)\}|\)
19:\(i_{F}.c\leq i_{x}.st<prevPath(fstout)\})\)do
20:\((t^{\prime},l^{\prime})\leftarrow(i_{x}.st+i_{x}.\lambda,l+i_{x}.\lambda)\)
21:\(\text{instrDom}(P^{\prime\prime}_{new}(v,k),(t^{\prime},l^{\prime}))\)
22:endfor
23:\(prevPath(fstout)\gets fstout\)
24:endfor
25:addOrmerge(\([v,P^{\prime\prime}_{new}(v,k)]\),\(nxtPLists\))
26:endfor
27:endfor
28:for all\(u\) in \(nxtPLists\)do
29:\((P(u,k),P_{new}(u,k))\leftarrow\)
30:\(Eval\,Anderge(P(u,k-1),P^{\prime}_{new}(u,k))\)
31:\(shtrstP[u]\gets P(u,k).last()\)
32:if\(P_{new}(u,k).size()>0\)then
33:\(newPaths++\)
34:endif
35:endfor
36:\(newPLists\gets nxtPLists\)
37:\(nxtPLists.clear()\)
38:endwhile
39:return \(shtrstP\)
```  
**Algorithm 2** Shortest Paths Detailed Algorithm  
Finally, in line 30, all \(P^{\prime}_{new}(u,k)\) at every vertex \(u\) available in \(nxtPLists\), are evaluated against their respective \(P(u,k-1)\) to obtain the non-dominated paths in hops 1 through \(k\) as \(P(u,k)\) and the new paths in current hop as \(P_{new}(u,k)\). The algorithm continues until the terminating conditions are met.