# Foremost Walks and Paths in Interval Temporal Graphs +
## 5 Min-Wait Foremost Walks in Interval Temporal Graphs
### Algorithm to Find \(mwf\) Walks
#### 5.4.2 Algorithm Description
Note that the new walk cannot have an earlier arrival time than the best known walk at \(v\) as the intervals are examined in non-decreasing order of arrival times, but it may have a lesser wait time. After a walk has been appended to the list of walks at \(v\), the function \(setupNewWClass\) examines all the neighbors of \(v\). If the start time of the last arriving walk class is in the middle of an available departure interval, \(intvl\) given, in the input graph \(G\) on an edge \((v,w)\), a new departure sub-interval of \(intvl\), say \(subIntvl\), is created. The start time of \(subIntvl\) is the arrival time of the walk and travel time same as that of the \(intvl\) (\(intvl.\lambda\)). This way, every walk originates at the \(start\) of an interval given in graph \(G\) or at start of a \(subIntvl\) that is a sub-interval of one of the intervals given in the input graph \(G\). This new \(subIntvl\) is inserted into the priority queue \(PQ\). In the \(removeMinIntvl\) function, the interval with minimum arrival time (when departing at the start of the interval) from \(intvl\,List\) and the top of \(PQ\) is returned. Algorithm 2 finds \(mwf\) walks from \(s\) to all other vertices in an interval temporal graph when all edge travel times are \(>\)0. Proof. : The algorithm examines all the departure intervals in non-decreasing order of arrival time, when departing at the start of the interval. For every interval, \(newIntvl\) in that order, it considers the best walk eligible for extension in this interval, as per Theorem 10, by obtaining the index for the previous walk (\(prevWIndex\)) in the list of walks at the departure vertex \(u\), in Step 13. It extends the \(prevWalk\) with departure in \(newIntvl\) only if this extension is beneficial as per Theorem 12. Once the walk is extended, it updates the \(lastExpAt\) for \(prevWalk\) for the edge \((u,v)\), so that subsequent departure intervals on \((u,v)\) are used for expanding \(prevWalk\) only if the resultant walks may be beneficial, as per Theorem 12. The extended walk is appended to the list of walks at \(v\) only if it is not dominated as per the dominance criterion of Equation (1). In addition, \(mwf\) walks at \(v\) are updated if the arriving walk is _better_ than the previous \(mwf\) walk, w.r.t \(mwf\) arrival at \(v\) or if it is the first walk to arrive at \(v\). Finally, the arriving walk at \(v\), \(newW\), is examined w.r.t all outgoing edges \((v,w)\). If for a departure interval \(I(s,e,\lambda)\) to any neighbor \(w\) we have \(I_{s}<newW.strTm\leq I_{e}\), a new sub-interval, \(subIntvl\), is created that has a start time of \(newW.strTm\) and inserted into \(PQ\). When such a \(subIntvl\) is the minimum interval among all the intervals from the input graph \(G\) and the \(subIntvl\)s created during the course of Algorithm 2, the \(newW\) gets the opportunity to expand at the start time of \(subIntvl\). Therefore, this algorithm starts at the start vertex and generates walks at all feasible departure instances w.r.t \(mwf\) walks criteria. Feasible departure intervals are examined in non-decreasing order of arrival times; therefore, every new walk generated has an arrival time \(\geq\) arrival time of any previously generated walk. No feasible non-dominated walk is missed due to Theorems 8-13. Every non-dominated walk generated is preserved and expanded as per Theorems 11-13. When a walk terminating at a vertex \(v\) is discovered that is the best among the walks arriving at \(v\) w.r.t \(mwf\) arrival, it is recorded as the \(mwf\) walk at \(v\). The algorithm terminates only when one of the following is true  
1. All intervals including the \(sub-intervals\) created during the course of Algorithm 2 have been examined. 2. \(mwf\) walks to all reachable vertices have been found and the arrival time when departing at the start of next interval being examined is bigger than the max arrival time of the \(mwf\) walks found. Therefore, examining any more intervals cannot give a better \(mwf\) walk.