A* algorithm

written by @marc_lelarge after this thread.

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

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)=\mathrm{\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$.

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$.

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^{\prime }=H\mathrm{\setminus }\{u\}$ and

$B=V\mathrm{\setminus }{H}^{\prime }$: (1) all nodes in

$H^{\prime }$ are at distance

$\ge \mathrm{dist}(u)$ from

$s$ and all nodes in

$B$ are at distance

$\le \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

$\mathrm{\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$:

$\mathrm{\forall }v\in B,\delta (v)=\mathrm{dist}(v)$. If this is not the case, by (2), there exists

$w\in H^{\prime }$ 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)\le \mathrm{dist}(u)$ contradicting the fact that

$\delta (w)\ge \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^{\prime }=H\mathrm{\setminus }\{u\}$ and

$B=V\mathrm{\setminus }{H}^{\prime }$. 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⇝v-w⇝u$. We have

$\delta (w)=\delta (v)+\ell (v,w)$. By the inductive hypothesis:

$\delta (v)=\mathrm{dist}(v)$ and

$\mathrm{dist}(w)\le \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)\le \mathrm{dist}(u)\le \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

$\le \mathrm{dist}(u)$ and (2) is correct. Suppose there exists

$x\in H^{\prime }$ 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⇝v-w⇝x$ so that

$\mathrm{dist}(v)=\delta (w)$ and since

$w\in H^{\prime }$:

$\mathrm{dist}(u)=\delta (u)\le \mathrm{dist}(w)=\delta (w)\le \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)$$

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)=\mathrm{\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$).

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 and GitHub code

Properties of A* algorithm

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$.

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\le 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\le 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.

A heuristic function is admissible if it never overestimates the actual cost to get to the goal:

$h(u)\le \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)\le \ell (u,v)+h(v)$.

Property : every consistent heuristic is also admissible.

Proof : By definition, we have

$h(u)\le \ell (u,v)+h(v)$ and we need to prove that

$h(u)\le \delta (u,t)$.
Consider a shortest path from

$u$ to

$t$ denoted

$(u,v_1,\dots ,v_k,t)$. We have

$h(v_k)\le \ell (v_k,t)+h(t)=\ell (v_k,t)$ as

$h(t)=0$. Then

$h(v_{k-1})\le \ell (v_{k-1},v_k)+h(v_k)\le \ell (v_{k-1},v_k)+\ell (v_k,t)$ and so on so that we get

$h(u)\le \ell (u,v_1)+\cdots +\ell (v_k,t)=\delta (u,t)$.

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.

Running Dijkstra's algorithm with the reduced lengths, if

$\pi$ is the current path from

$s$ to

$v$, we have:

$$\begin{array}{rcl}{\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}\ast }(v)+h(v)-h(s).\end{array}$$
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$.

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:

Property : if the heuristic is admissible, then A* always finds a shortest path.

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\le 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)\le \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})\le \delta (v_{i+1},t)$ (by admissibility). Hence, we get

$\delta (s,t)\le \mathrm{dist}(t)\le \delta (s,v_{i+1})+\delta (v_{i+1},t)=\delta (s,t)$, a contradiction.

tags: public agreginfo