- graph undirected
- Directed graph with non-negative weights
- Directed graph with all types of weights
- Based on a heuristic
- Algorithm A *
- Anytime Repairing A * (ARA *)
- Anytime Dynamic A *
- D *
- Fringe
- Fringe Saving A * (FSA *)
- Generalized Adaptive A * (GAA *)
- Incremental heuristic search
- Informational search
- Iterative deepening A * (IDA *)
- Jump point search
- Lifelong Planning A * (LPA *)
- Multiplier-accelerated A * (MAA *)
- New Bidirectional A * (NBA *)
- Simplified Memory bounded A * (SMA *)
- Realtime A *
- Time-Bounded A * (TBA *)

- Shortest path resolution with Excel
- Switch from a multi-source / sink to a single

## Path search

The **path search**, commonly called * pathfinding *consists in finding how to move in an environment between a starting point and an ending point while taking into account various constraints.

**Definition of a valued graph**

A valued graph is a graph with the arcs of which we associate a real number called the length of the arc.

We denote by w (x, y) the length of the arc (x, y) between the vertices x and y.

By analogy with the adjacency matrix, we can represent a graph valued by a square matrix, the coefficients of which correspond to the valuation of the arcs.

Let be a valued graph whose vertices have been numbered from 1 to n. The valuation matrix of G is the square matrix M = m_{ij}, of size n * n, defined by

Here is an example:

We can therefore deduce the following linear program, with x_{ij}= 1 if the arc is part of the shortest path, 0 otherwise:

- minimize with A the set of arcs
- subject to

and for all *i*,

Although it is linear programming, this method can be very expensive in memory, and even impossible to set up in certain cases (for example if it is a distributed system). Another method to know the shortest path would be to know the shortest of all the paths from one vertex to another.

We define the weight of a path **c = (u,…, v)**

as the sum of the weights of the arcs which constitute it noted **w (c).**We then define the minimum distance (shortest path) between two vertices u and v by:

We would like to have a capable method, for any graph and for any pair of vertices * x* and

*, to determine the shortest path between them. For this, we must understand and characterize as well as possible the structure of a solution: what are the properties of a shorter path?*

**y****Lemma of Koenig.** A shorter path between 2 vertices is elementary. A path is elementary if each of the peaks of the route is visited only once.

Listing all the paths to determine the shortest one reveals a serious flaw: its execution time. If the number of elementary paths is finite, it nonetheless remains very large, of the order of * not!* on an order graph

*.*

**not**## Suboptimal problem

We need a second, fundamental property, the *sub-optimality (see Dynamic Programming)*. It's about noticing that being a shortest way is recursive : a shortest path sequence is still a shortest path between its endpoints. Or if the fastest route between * u *and

*goes through 2 peaks*

**v***and*

**x***, this route necessarily takes the shortest path between*

**y***and*

**x**

**y.**Yes * p = (u,…, v)* is a shorter way between

*and*

**u***, then for any summit*

**v***on the road*

**x***:*

**p**- the subpath of
up to**p**,**x**, is a shorter path of**(u,…, x)**To**u****x** - the subpath of
since**p**,**x**, is a shorter path of**(x,…, v)**To**x****v**

For the absurd let us suppose that there exists for example between * u* and

*a path*

**x***of length strictly less than that of*

**q***. So we can build a new way*

**p = (u,…, x,…, v)***Between*

**p '***and*

**u***substituting*

**v***on*

**q***in the way*

**(u,…, x)***. The length of*

**p***is then strictly lower than that of*

**p '***, which contradicts that*

**p***is a shorter way of*

**p***To*

**u***.*

**v**## Tree of paths

There is a tree shortest paths from a starting vertex to all others. Suppose the graph is connected, the edges are undirected, and the weights are non-negative. We expand a vertex cloud, starting with s and eventually covering all vertices. We store at each vertex v a label d (v) representing the distance of v from s in the subgraph consisting of the cloud and its adjacent vertices. At each step: we add to the cloud the vertex outside the cloud with the smallest distance label; we update the labels of the vertices adjacent to u (see tree covering).

Consider an edge e = (u, z) such that u is the most recently added vertex to the cloud and z is not in the cloud. The relaxation of edge e updates the distance d (z) as follows: d (z) ← min {d (z), d (u) + weight (e)}