Pathfinding


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

  1. Linear programming
  2. Dijkstra, DAG and Bellman
  3. Floyd-Warshall

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).
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:
13
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}

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 way 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:
12

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

Publicités