Pathfinding


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 =mij, size n*n, is defined by: mij=w(i,j) if (i,j) exists, +inf otherwise.
Here is an example:
14
We can therefore deduce the following linear program, with xij=1 if the arc is part of the shortest path, 0 otherwise:
  • minimize \sum_{ij \in A} w_{ij} x_{ij} with A the set of arcs
  • subject to x \ge 0

and for all i, \sum_j x_{ij} - \sum_j x_{ji} = \begin{cases}1, &\text{if }i=s;\\ -1, &\text{if }i=t;\\ 0, &\text{ otherwise.}\end{cases}

 LPpath
LPpath2
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 u and v, then for each vertex x on p :

  • the path p from x, (u,…,x), is a shortest path between u and x
  • the path from p to x, (x,…,v), is a shortest path between x and 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)}

relax1

realx2

Publicités