# 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:
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 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)}

Publicités
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 3, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8676804900169373, "perplexity": 672.1293346897222}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-30/segments/1531676592150.47/warc/CC-MAIN-20180721012433-20180721032433-00127.warc.gz"}