# A* algorithm
written by [@marc_lelarge](https://twitter.com/marc_lelarge) after this [thread](https://x.com/marc_lelarge/status/1876669707786576027).
:::warning
We always assume that the graph we consider is connected (and finite) so that there is always a shortest path between $s$ and $t$.
:::
## Recap: Dijkstra's shortest-path algorithm
See Chapter 4 of [Algorithms - Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani](https://github.com/eherbold/berkeleytextbooks/blob/master/Algorithms%20-%20Sanjoy%20Dasgupta%2C%20Christos%20H.%20Papadimitriou%2C%20and%20Umesh%20V.%20Vazirani.pdf)
:::info
**Dijkstra's shortest-path algorithm**
Input: Graph $G=(V,E)$; positive edge lengths $\{\ell_e, e\in E\}$; vertex $s\in V$
Output: For all vertices $u$ reachable from $s$, the distance from $s$ to $u$: $\mathrm{dist}(u)$
for all $u\in V$:
$\mathrm{dist}(u) = \infty$
$\mathrm{prev}(u) = \mathrm{nil}$
$\mathrm{dist}(s) = 0$
$H = \mathrm{makequeue}(V, \mathrm{dist})$ (using dist-values as keys)
while $H$ is not empty:
$u = \mathrm{deletemin}(H, \mathrm{dist})$
for all edges $(u,v) \in E$:
if $\mathrm{dist}(v)>\mathrm{dist}(u) +\ell(u,v)$:
$\mathrm{dist}(v) = \mathrm{dist}(u) +\ell(u,v)$
$\mathrm{prev}(v) = u$
$\mathrm{decreasekey}(H,v)$
:::
At the end of the algorithm, $\mathrm{prev}$ will hold for each node $u$ the identity of the node immediately before it on the shortest path from $s$ to $u$.
The right data structure for $H$ is a **priority queue** which maintians a set of elements (nodes) with associated numeric key values ($\mathrm{dist}$) and supports the following operations:
- *Insert.* Add a new alement to the set
- *Decrease-key.* Accommodate the decrease in key value of a particular element.
- *Delete-min.* Return the element with the smallest key, and remove it from the set.
- *Make-queue.* Build a priority queue out of the given elements, with the given key values.
Note that each node is added once in $H$ before the while loop and removed from $H$ during an iteration of the while loop. For each node $u$, $\mathrm{dist}(u)$ can only decrease in this algorithm and is always an upper bound for the true distance from $s$ to $u$.
:::info
**Property :** when $u$ is removed from $H$, then $\mathrm{dist}(u)$ is the correct distance from $s$ to $u$ and $\mathrm{prev}(u)$ is the correct node before $u$ in the shortest path from $s$ to $u$.
:::
:::success
**Proof :** This can be proved by induction with the following inductive hypothesis: at the end of each iteration of the while loop, the following conditions hold with $u=\mathrm{deletemin}(H, \mathrm{dist})$, $H'=H\backslash \{u\}$ and $B = V\backslash H'$: (1) all nodes in $H'$ are at distance $\geq \mathrm{dist}(u)$ from $s$ and all nodes in $B$ are at distance $\leq \mathrm{dist}(u)$ from $s$, and (2) for every node $v$, the value $\mathrm{dist}(v)$ is the length of the shortest path from $s$ to $v$ whose intermediate nodes are constrained to be in $B$ (if no such path exists, the value is $\infty$).
The base case is straightforward since $s$ is the first removed element from $H$ so that $B=\{ s\}$.
We denote by $\delta(v)$ the true distance between $s$ and $v$.
Points (1) and (2) of the inductive hypothesis imply that all nodes $v\in B$ are at $\mathrm{dist}(v)$ from $s$: $\forall v\in B, \delta(v) =\mathrm{dist}(v)$. If this is not the case, by (2), there exists $w\in H'$ on the shortest path from $s$ to $v$. Since the edge lenghts are positive, the partial path from $s$ to $w$ is the shortest path between $s$ and $w$ and its lenght $\delta(w)$ is strictly less than the distance $\delta(v)$ between $s$ and $v$ but by (1) $\delta(v) \leq \mathrm{dist}(u)$ contradicting the fact that $\delta(w)\geq \mathrm{dist}(u)$. As a result, nodes $v\in B$ have been removed from the queue in increasing order of $\mathrm{dist}(v)=\delta(v)$.
Assume now that the inductive hypothesis is correct and let $u=\mathrm{deletemin}(H)$, $H'=H\backslash \{u\}$ and $B=V\backslash H'$. Let $v$ be the last node in $B$ on the shortest path from $s$ to $u$ and $w$ the node on this path neighbor of $v$ and closer to $u$: $s \leadsto v - w \leadsto u$. We have $\delta(w) = \delta(v) +\ell(v,w)$. By the inductive hypothesis: $\delta(v) = \mathrm{dist}(v)$ and $\mathrm{dist}(w) \leq \mathrm{dist}(v)+\ell(v,w) =\delta(v) +\ell(v,w)$ hence $\mathrm{dist}(w) = \delta(w)$. But since $u=\mathrm{deletemin}(H)$, we have $\delta(u)\leq \mathrm{dist}(u)\leq \mathrm{dist}(w) = \delta(w)$, so that $u=w$ and we proved $\mathrm{dist}(u)=\delta(u).$ Clearly all nodes in $B$ are at distance $\leq \mathrm{dist}(u)$ and (2) is correct. Suppose there exists $x\in H'$ with $\delta(x)< \mathrm{dist}(u)=\delta(u)$. We can apply the same argument as above by considering the shortest pasth form $s$ to $x$ and the last node $v$ in $B$: $s\leadsto v - w \leadsto x$ so that $\mathrm{dist}(v) = \delta(w)$ and since $w\in H'$: $\mathrm{dist}(u)=\delta(u)\leq\mathrm{dist}(w)= \delta(w) \leq \delta(x)$, a contradiction. Hence we proved (1).
:::
## Modifying Dijkstra's shortest-path algorithm to get A* algorithm
Instead of computing all the shortest paths from $s$, we now have a target $t$ and want to compute efficiently the shortest path from $s$ to $t$.
We have access to a heuristic fucntion $h(u)$ that estimates the length of the path from any node $u$ to the target $t$.
The A* algorithm is a simple variation of the Dijkstra's algorithm with a single modification: the priority in the queue is now the function:
$$
\mathrm{dist}(u) + h(u)
$$
:::info
**A\* algorithm**
Input: Graph $G=(V,E)$; positive edge lengths $\{\ell_e, e\in E\}$; vertex $s\in V$; a vertex $t\in V$ and an associated heuristic function $h(u)$ estimating the distance from $u$ to $t$.
Output: under some conditions on the heuristic $h$, a shortest path from $s$ to $t$.
for all $u\in V$:
$\mathrm{dist}(u) = \infty$
$\mathrm{prev}(u) = \mathrm{nil}$
$\mathrm{dist}(s) = 0$
$H = \mathrm{makequeue}(V, \mathrm{dist}+h)$ (using keys: $\mathrm{dist}(u)+h(u)$)
while $H$ is not empty:
$u = \mathrm{deletemin}(H, \mathrm{dist}+h)$
if $u = t$:
break
for all edges $(u,v) \in E$:
if $\mathrm{dist}(v)>\mathrm{dist}(u) +\ell(u,v)$:
$\mathrm{dist}(v) = \mathrm{dist}(u) +\ell(u,v)$
$\mathrm{prev}(v) = u$
if $v \notin H$:
$\mathrm{insert}(H,v)$
$\mathrm{decreasekey}(H,v)$
:::
We still have that for each node $u$, $\mathrm{dist}(u)$ can only decrease and is always an upper bound for the true distance from $s$ to $u$. Note that $s$ is the first node removed from $H$ (and nerver added back to $H$).
:::warning
If the heuristic function is zero: $h(u)=0$, A* reduces to Dijkstra's algorithm.
In this case, it follows from previous proof that when $\mathrm{dist}(v)$ is decreased, $v$ is always in $H$, hence there is no insertion in $H$ and all steps are the same in both algorithms.
:::
### A comprehensive path-finding library in javascript.
Accessible here: [Demo](https://qiao.github.io/PathFinding.js/visual/) and [GitHub code](https://github.com/qiao/PathFinding.js)
## Properties of A* algorithm
:::info
**Lemma :** For an optimal path $s=v_0,v_1,\dots, v_k=t$, if $v_i$ is removed from $H$ and all the $v_j$'s for $j<i$ have been removed from $H$ then $\mathrm{dist}(v_i)$ is the true distance between $s$ and $v_i$ and $v_0,\dots, v_i$ will never be inserted back into $H$.
:::
:::success
**Proof :** the claim is clearly true for $v_0=s$. Assume it is true for all $v_0,v_1, \dots, v_{i-1}$ and $v_i$ is removed from $H$. Between the removal of $v_{i-1}$ and $v_i$ some other nodes might have been removed from $H$ but since $\mathrm{dist}(v_j) = \delta(s,v_j)$ for all $j\leq i-1$, these removals will not modify any of the $\mathrm{dist}(v_j)$ (and not add them back to $H$). Now after removal of $v_{i-1}$, since $v_i$ is a neighbor, we have $\mathrm{dist}(v_i) = \mathrm{dist}(v_{i-1}) + \ell(v_{i-1}, v_i)=\delta(s,v_i)$.
:::
Consider a variant of A*, where we remove the `break`. This variant of A* terminates, i.e. $H$ will become empty after a finite number of iterations since the number of possible values for all the $\mathrm{dist}(u)$ is finite. Moreover, thanks to previous Lemma, in this variant of A*, when $v_i$ is last removed from $H$ then $\mathrm{dist}(v_i)$ is the true distance between $s$ and $v_i$ (and all the $v_j$ for $j\leq i$ have been removed from $H$). In particular, the only way for A* to fail to return an optimal path is because it removes the target $t$ from $H$ too early. Under some conditions on the heuristic, we can guarantee that this will nerver happen.
:::warning
A heuristic function is **admissible** if it never overestimates the actual cost to get to the goal: $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ is the distance between $u$ and the goal $t$.
A heuristic is **consistent (or monotone)** if for each edge $(u,v)\in E$, $h(u) \leq \ell(u,v) + h(v)$.
:::
:::info
**Property :** every consistent heuristic is also admissible.
:::
:::success
**Proof :** By definition, we have $h(u) \leq \ell(u,v) + h(v)$ and we need to prove that $h(u) \leq \delta(u,t)$.
Consider a shortest path from $u$ to $t$ denoted $(u,v_1,\dots, v_k,t)$. We have $h(v_k)\leq \ell(v_k,t)+h(t)= \ell(v_k,t)$ as $h(t)=0$. Then $h(v_{k-1})\leq \ell(v_{k-1},v_k)+h(v_k)\leq \ell(v_{k-1},v_k)+\ell(v_k,t)$ and so on so that we get $h(u)\leq \ell(u,v_1)+\dots +\ell(v_k,t)=\delta(u,t)$.
:::
:::info
**Property :** A* is equivalent to Dijkstra’s algorithm on a graph with reduced lengths $c(u,v) = \ell(u,v) -h(u) +h(v)$. Note that, since Dijkstra’s algorithm requires arc costs to be nonnegative, the heuristic needs to be consistent.
:::
:::success
Running Dijkstra's algorithm with the reduced lengths, if $\pi$ is the current path from $s$ to $v$, we have:
\begin{eqnarray*}
\mathrm{dist}_{\mathrm{Dijkstra}}(v) &=& \sum_{(u,w)\in \pi} c(u,w)\\
&=& \sum_{(u,w)\in \pi} \ell(u,w) + h(v) - h(s)\\
&=&\mathrm{dist}_{\mathrm{A*}}(v)+h(v)-h(s).
\end{eqnarray*}
The result follows since $h(s)$ is a constant and the fact that if $\mathrm{dist}_{\mathrm{Dijkstra}}(v)$ is updated then $v\in H$.
:::
:::warning
As a consequence A* returns an optimal path with reduced costs but since $h(t)=0$, this optimal path is also optimal for the original cost.
:::
It turns out, we only need to have an admissible heuristic for A* to find shortest paths:
:::info
**Property :** if the heuristic is admissible, then A* always finds a shortest path.
:::
:::success
This can be proved by contradiction. Assume that the path retruned by A* between $s$ and $t$ is not optimal, i.e. $\mathrm{dist}(t) >\delta(s,t)$ when $t$ is removed from $H$. Consider $H$ just before $t$ is chosen. Denote by $s=v_0,v_1,\dots, v_k=t$ an optimal path from $s$ to $t$. Since $s\notin H$, $\mathrm{dist}(s)=0$ and $t\in H$, by previous Lemma, there exists a node $v_i$ such that for all $j\leq i$, $\mathrm{dist}(v_j)=\delta(s,v_j)$ and $v_{i+1}\in H$. But since $t$ has been chosen and $h(t)=0$, we have $\mathrm{dist}(t) \leq \mathrm{dist}(v_{i+1})+h(v_{i+1})$. But we have $\mathrm{dist}(v_{i+1})=\delta(s,v_{i+1})$ (since $v_i$ has been removed from $H$ and $\mathrm{dist}(v_i)=\delta(s,v_i)$) and $h(v_{i+1})\leq \delta(v_{i+1},t)$ (by admissibility). Hence, we get $\delta(s,t)\leq \mathrm{dist}(t) \leq \delta(s,v_{i+1}) + \delta(v_{i+1},t) = \delta(s,t)$, a contradiction.
:::
###### tags: `public` `agreginfo`
Sign in with Wallet
Connect another wallet