## From one source:

- Undirected graph
- Unweighted graph
- Directed graph with nonnegative weights
- Directed graph with any weights
- Heuristic-based

## From all sources:

- Undirected graph
- Directed graph
- Stochastic graph

## Any-angle path planning / robot navigation :

- A*-based
- RRT-based

## Resolution methods:

- Shortest path problem with Excel

## Definition

The * pathfinding *consists to find how to move, in a specific environment, between a starting point to an end point.

**Definition of a valued graph**

This is a graph whose arcs/edges are associated with a real number called length.

Note w(x,y) the length of the arc/edge (x,y). It shows distances, costs, etc.

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

The matrix M =m_{ij}, size n*n, is defined by: m_{ij}=w(i,j) if (i,j) exists, +inf otherwise.

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 is very expensive in memory, and even impossible to implement in some cases (for example in a distributed system). Another method to compute the shortest path would be to know the smallest of all the paths from one vertex to another.

Let **c=(u,…,v) be the total length of a path**

as the sum of all length **w(c) **constituting the path.** We define the minimum distance (shortest path) between two vertices u and v by: **min w(c) if c exists, +inf otherwise.

We would like to have a method that can, for any graph and any pair of x and y vertices, determine the shortest path between them. For this we need to understand and characterize the structure of a solution: what are the properties of a shortest path?

**Lemma of Koenig. **A shortest path of 2 vertices is elementary. A path is elementary if each vertex of the course is visited once.

The fact of listing all the paths to determine the shortest reveals a serious defect: its execution time. If the number of elementary paths is non-infinite, it remains nonetheless very large, of the order of n! on a graph of order n.

## Suboptimality

We need a second property, fundamental, suboptimality (see Dynamic Programming). It is worth to note that being a shorter path is recursive: a sequence of a shorter path is still a shorter path between any ends. Or if the shortest path between u and v go through 2 vertices x and y, this path necessarily takes the shortest path between x and y.

If * p=(u,…,v)* is a shortest path between

*and*

**u***, then for each vertex*

**v***on*

**x***:*

**p**- the path
from**p**,**x**, is a shortest path between**(u,…,x)**and**u****x** - the path from
to**p**,**x**, is a shortest path between**(x,…,v)**and**x****v**

By contradiction suppose that there exists a path q between u and x shorter than p = (u, …, x, …, v). Then we can construct a new path p’ between u and v by substituting q for (u, …, x) in path p. The length of p’ is then strictly inferior to p, which contradicts p being a shortest path from u to v.

## Tree of shortest paths

There is a tree of shortest paths from a start vertex to all others. Assume the graph is connected, edges are undirected and weights are nonnegative. We grow a cloud of vertices, beginning with s and eventually covering all the vertice. We store with 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 u 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 vertex most recently added to the cloud and z is not in the cloud. The relaxation of edge e updates distance d(z) as follows: d(z) ← min {d(z), d(u) + weight(e)}