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

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

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

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

_{ij}=w(i,j) if (i,j) exists, +inf otherwise.

_{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:**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)}