- From one source:
- Fredman & Tarjan
- Ahuja et al.
- From all sources:
Slides from my course (see Shortest path problem) : Click here
- Linear programming
- Dijkstra, DAG and Bellman
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:
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:
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:
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.