**From one source:**- Dijkstra
- Dantzig
- DAG
- Ford-Bellman
- A*
- Fredman & Tarjan
- Gabow
- Ahuja et al.

**From all sources:**- Floyd-Warshall
- Williams
- Johnson
- Pettie

*Slides from my course (see Shortest path problem) : Click here*

## Definition

The * pathfinding *consiste à trouver is 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).

_{ij}, size n*n, is defined by:

_{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*,

**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:**

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.

We need a second property, fundamental, suboptimality (see Dynamic Programming). It is worth noting that being a shorter path is recursive: a sequence of a shorter path is still a shorter path between its 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.