# Motivation

A* Search is an algorithm that uses heuristics to speed up shortest path queries. To make a correct query with A* from $s$ to $t$ on a Graph $G=(V, E)$ we need a heuristic $\pi_t(v)$ that is a lower bound for the real distance to t: $\forall v\in V: \pi_t(v) \leq dist(v, t)$. The better $\pi_t(v)$ is (= the bigger the heuristic value is), the better is the speedup.

Graphs with public transit (Public Transit Graphs, PTG) have edges for fast connections that only operate a few times a day. This means that depending on the departure time, the travel time of the edge is either very short or very long (if you depart shortly before the train departs, you can take the train, if you depart after the train departed you either have to wait for the next connection or you have to walk). This makes it hard to find good lower bounds of such edges due to their high fluctuation of their travel time. Consequently, A* does not result in a good speedup on such graphs.

The main idea of this approach is to identify a set of edges $L_1 \subset E$ with a high fluctuation of travel time and to find a good heuristic for $\underline{G}=(V, E \setminus L_1)$. We can then query differently on these two sets using a combination of A* in $\underline{G}$ and Dijkstra in $\overline{G}=(V, L_1)$ … *or something like that @TODO.

# Assumptions & Conditions

Given a graph $G=(V,E)$

Given a subset $L_0 \subseteq E$

Given a subset $L_1 \subseteq E$ with $L_0 \cap L_1 = \emptyset$

and we define $L_{0,1} = L^*=(E \setminus L_0)\setminus L_1$

### Levels of Layers and Edges

We also call the subsets $L_i$ layers with level $i$.

We define levels of edges $e_i$ in a path $P=(e_0, \dots, e_k)$ as follows:

We denote the level of a path $level(P)=k$ if $\forall e \in P : level(e) =k$.

For $L_0$ and $L_1$ the layer condition is true:

alternatively:

%

### Heuristics

We also require a heuristic $\pi_t(v, l)$:

• $\pi_t(v,0)$ is an admissable heuristic with $\pi_t(t, 0)=0$

# First Take: The most naive and Simple PTG-A*

Q is a priority function, pi(v,l) is a heuristic function, d[v] shortest distance to v found

The Algorithm is a normal A* search algorithm on edges $e \in L_0$ and a normal Dijkstra on edges $e \in L_1$. The edges $e \in L^*$ are considered as edges from either $L_0$ or $L_1$ depending on what the current level is.　Note, that there is no stopping criteria whatsover yet und the current approach will check and try to relax all reachable edges.

## Correctness

Is PTG-A* correct and finds the shortest path from $s$ to $t$? Intuition says yes. There’s not stopping criteria. We’re doing A* or Dijsktra on the whole graph and we should find the shortest path between $s$ and $t$ because of line 7:

d[v] = d[u] + len(e)


A* is correct.

#### Case 2: Shortest path $P=\underline{P_s} + \overline{P}$

A*, then correct Dijsktra.

#### Case 3: Shortest path $P=\underline{P_s} + \overline{P} + \underline{P_t}$

A, then Dijkstra, then A.

# Second Take: Stopping PTG-A*

Simple PTG-A* is basically a mix of a Dijsktra and A* that traverses the whole graph and all its edges. Can we stop the search after relaxing our target $t$? Namely, can we add line 5 as follows?

## Correctness

We will find a proof by contradiction - but first a neat corollar!

### Corollar Shortest-Path-Order

Let $P=(e_0, \dots, e_k)\equiv (v_0, \dots, v_{k+1})$ be a shortest path from $v_0$ to $v_{k+1}$ and $level(P)=0$. For every vertex $v_i$ it is $key(v_i)\leq key(v_{i+1})$.

Proof:

Which is exactly the definition of feasibility of heuristics!

Back to trying to prove correctness of PTG-A*

### Case 1: Shortest path $P$ with $level(P) = 0$

Let $\hat{P} \neq P$ be the shortest path found by PTG-A* and $len(\hat{P})\gt len(P)$.

If $\forall e \in \hat{P}: e \in L_0 \cup L^*$ it is a contradiction to the correctness of A*. Therefore, $\exists \hat{e}=(u,v)\in \hat{P} : \hat{e} \in L_1$. With no loss of generality we assume

with $level(\overline{P}) = 1$ and $level(\underline{P}) = 0$.

#### If $|\underline{P}| \gt 0$

@TODO why are IPE PNGs so awful?

Let vertex $w$ be the first vertex that is in $\hat{P} \cap P$. Vertex $v$ definitely exists because vertex $t \in \underline{P} \cap P$. Let $\hat{e}=(v,w)\in \hat{P}$ and $e=(u,w)\in P$. When $\hat{e}$ is relaxed, vertex $w$ will be updated in the queue with $\widehat{key}(w)=len(\hat{P}(s,w)) + \pi_t(w)$. But when relaxing edge $e$, vertex $w$ will be updated with $key(w) = len(P(s,w)) + \pi_t(w) \leq \widehat{key}(w)$. As the key values in $P$ are monotonically increasing and $key(w)$ is smaller than $\widehat{key}(w)$ it will be extracted from the queue before with the correct distance. This is a contradiction ↯

#### If $|\underline{P}| = 0$

Let edge $\hat{e}=(v,t)$ be the last edge in $\hat{P}$ and edge $e=(u,t)$ the last edge in $P$. When $\hat{e}$ is relaxed, vertex $t$ will be updated in the queue with $\widehat{key}(t) = len(\hat{P} \geq dist(s,t))$. But when relaxing edge $e$, vertex $t$ will be updated with $key(t) = len(P) = dist(s,t) \leq \widehat{key}(t)$. As the key values in $P$ are monotonically increasing and $key(w)$ is smaller than $\widehat{key}(w)$ it will be popped (?) from the queue before with the correct distance. This is a contradiction ↯

### Case 2: Shortest path $P = \underline{P_s} + \overline{P} + \underline{P_t}$

The proof in Case 1 makes use of the fact that key values in a shortest path are monotonically increasing. More importantly, when a vertex with key of value $x$ is extracted from the queue and $key(e_i) \leq x$, then we can be sure that all vertices $e_j, j \lt i$ were already relaxed before. How does this change with a shortest Path that has edges from $L_1$.

### Observations of Key Values on Shortest Paths $P = \underline{P_s} + \overline{P} + \underline{P_t}$

1. When relaxing edges $E_i \in \overline{P}$ the key values are always smaller than edges $e_i \in \overline{P_t}$
2. 1+2 $\Rightarrow \overline{P} + \underline{P_t}$ is monotonically increasing
3. But we know the key values when visiting $\underline{P_s}$ and $\underline{P_t}$ are also increasing. This means that as soon we relax an edge $e$ from $\overline{P}$, we will find the path $P(s, e)$

Let $\hat{P} \neq P$ be the shortest path found by PTG-A* and $len(\hat{P})\gt len(P)$. Let edge $e=(u,v)$ be the last edge of $\underline{P_s}$.

It is $\hat{P} = \underline{\hat{P}_s} + \overline{\hat{P}}$. Vertex $t$ was found and relaxed when extracting $t$ with $\widehat{key}(t) = \hat{d}[t] = len(\hat{P}(s, t))$. We know $\widehat{key}(t) \leq key(v)=len(P(s, v)) + \pi_t(v) \gt dist(s,t)$ because otherwise (see the key value observations) the PTG-A* would have found the shortest path $P$.

But when relaxing edge $e$ we update vertex $v$ with $key(v) = len(P(s,v)) + \pi_t(v) \leq dist(s,t)$ so it has to be extracted before vertex $t$ is extracted through path $\hat{P}$. This is a contradiction ↯

## Adding Labels to the Queue

The algorithm PTG-A* updates labels of vertices (as in line 12, 16, 20). The algorithm works correctly if you update a label $label(v) = (v, l_{max}, l_{curr}, key(v))$ with $label'(v) = (v, l'_{max}, l'_{curr}, key'(v))$ if $l_{max} = l'_{max} \wedge l_{curr} = l'_{curr} \wedge key'(v) \lt key(v)$. Otherwise, we will add the new label additionally to the old one to the queue. But there should be some cases in which we can also update a label even though $l_{max} \neq l'_{max} \wedge l_{curr} \neq l'_{curr}$.

Therefore, we analyze all cases where

• $label_{old}(v) = (v, x, y, key_{xy}(v))$ is already in the queue and
• $label_{new}(v) = (v, w, z, key_{wz}(v))$ is the new label we want to update/add to the queue.

In every case we have to check whether we need to

• keep $label_{old}(v)$ or
• remove $label_{old}(v)$ and
• add $label_{new}(v)$ or
• ignore $label_{new}(v)$

Let $P$ be the shortest path from $s$ to $t$. Let $P_{old}$ and $P_{new}$ be the paths from $s$ to vertex $v$ that create $label_{old}(v)$ and $label_{new}(v)$.

### $key_{00}$

#### if $key_{00} \lt key_{xz}$

• remove $label_{old}(v)$
• add $label_{new}(v)$

Proof:

Therefore, the shortest path $P$ does not use the subpath $P_{old}$. Thus, $P_{old}$ cannot be a subpath of $P$ and we can remove $label_{old}(v)$.

#### if $key_{00} \gt key_{10}$

• keep $label_{old}(v)$
• ignore $label_{new}(v)$

Proof:

Therefore, the shortest path $P$ does not use the subpath $P_{new}(s, v)$. (Actually, the algorithm will not even attempt to ever add $label_{new}(v)$ because of line 7 in the code).

Thus, $P_{new}$ cannot be a subpath of $P$ and we can ignore $label_{new}(v)$.

#### if $key_{00} \gt key_{11}$

• If $key_{00} - \pi_t(v, 0) \gt key_{11}$
• keep $label_{old}(v)$
• ignore $label_{new}(v)$

Proof:

Therefore, the shortest path $P$ does not use the subpath $P_{new}(s, v)$. Thus, $P_{new}$ cannot be a subpath of $P$ and we can ignore $label_{new}(v)$.

• If $key_{00} - \pi_t(v, 0) \lt key_{11}$
• remove $label_{old}(v)$
• add $label_{new}(v)$

Proof:

Therefore, the shortest path $P$ does not use the subpath $P_{old}(s, v)$. Thus, $P_{old}$ cannot be a subpath of $P$ and we can remove $label_{old}(v)$.

### $key_{11}$

#### if $key_{11} \gt key_{xz}$

• keep $label_{old}(v)$
• ignore $label_{new}(v)$

Proof:

Therefore, the shortest path $P$ does not use the subpath $P_{new}(s, v)$. Thus, $P_{new}$ cannot be a subpath of $P$ and we can ignore $label_{new}(v)$.

#### if $key_{11} \lt key_{x0}$

• If $key_{11} \lt key_{x0} - \pi_t(v, 0)$
• remove $label_{old}(v)$
• add $label_{new}(v)$

Therefore, $P_{old}$ cannot be a subpath of $P$ and we can remove $label_{old}(v)$.

• If $key_{11} \gt key_{x0} - \pi_t(v, 0)$
• keep $label_{old}(v)$
• ignore $label_{new}(v)$

Therefore, $P_{new}$ cannot be a subpath of $P$ and we can ignore $label_{new}(v)$.

### $key_{10}$

#### if $key_{10} \lt key_{xz}$

• remove $label_{old}(v)$
• add $label_{new}(v)$

Therefore, $P_{old}$ cannot be a subpath of $P$ and we can ignore $label_{old}(v)$.

#### if $key_{10} \gt key_{00}$

• keep $label_{old}(v)$
• ignore $label_{new}(v)$

Therefore, $P_{new}$ cannot be a subpath of $P$ and we can ignore $label_{new}(v)$.

#### if $key_{10} \gt key_{11}$

• If $key_{10} - \pi_t(v, 0) \lt key_{11}$
• remove $label_{old}(v)$
• add $label_{new}(v)$

Therefore, $P_{old}$ cannot be a subpath of $P$ and we can remove $label_{old}(v)$.

• If $key_{10} - \pi_t(v, 0) \gt key_{11}$
• keep $label_{old}(v)$
• ignore $label_{new}(v)$

Therefore, $P_{new}$ cannot be a subpath of $P$ and we can ignore $label_{new}(v)$.

### Conclusion Regarding Dominating Labels

Looking at the results above we either remove $label_{old}$ and add $label_{new}$ or we keep $label_{old}$ and ignore $label_{new}$. Therefore, we either update (remove and add) or keep (keep and ignore) the label.

 $key_{00}$ $\lt key_{xy}$ update $\gt key_{10}$ keep $\gt key_{11} + \pi$ keep $\lt key_{11} + \pi$ update $key_{11}$ $\gt key_{xy}$ keep $\lt key_{x0} - \pi$ update $\gt key_{11} - \pi$ keep $key_{10}$ $\lt key_{xy}$ update $\gt key_{00}$ keep $\lt key_{11} + \pi$ update $\gt key_{11} + \pi$ keep

Due to line 7 in the code, many cases do not even need to be checked because the algorithm would never try to add those labels anyways.