- 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

Contenus

Toggle## 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 about a distributed system). Another method of knowing the shortest path would be to know the smallest 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 *suboptimality (see Dynamic Programming)*. It is a matter of noticing that being a shorter path is recursive: a sequence of a shorter path is still a shorter path between its ends. 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 There is a tree showing the shortest paths from one starting point to all the others. Suppose the graph is connected, the edges are not directed, and the weights are non-negative. We develop a cloud of vertices, starting with s and eventually covering all the vertices. We store at each vertex v a label d (v) representing the distance of v from s in the subgraph made up of the cloud and its adjacent vertices. At each step: we add to the cloud the top outside the cloud with the smallest distance label; we update the labels of the vertices adjacent to u (see spanning tree).

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)}