Shortest path problem

A shortest path in the graph theory, a path between two different nodes of a graph that has the minimum length with respect to a weight function. Do the edges in the graph all the weight 1, ie, it is the shortest path - path with the least possible number of edges between and.

In the literature, the problem is often referred to as a shortest path problem.

Complexity

In general, the determination of a shortest path is a serious problem: The decision problem

"Does a graph a - path of length? "

Is NP-complete, accordingly, generally also a shortest path probably not be found in polynomial time. If a graph has a Hamiltonian path, then this is a shortest - path with respect to the weight function. Here already is the question of the existence of such a path an NP -complete problem.

In many special cases the determination of shortest paths in polynomial time is possible in spite of the complexity of the problem. The main limitation concerns here the weight function:

For conservative weight functions, shortest paths in polynomial time can be determined, this can be used, for example, the Bellman - Ford algorithm.

If you continue to additionally even non-negativity required by the objective function, calls, so can be solved much faster still the problem with the A * algorithm or the Dijkstra's algorithm.

Variations of the problem

Apart from the determination of a shortest - path there are several more, but very similar problems:

This variant of the problem of the shortest paths is concerned with the problem how to calculate the shortest paths between a given start node and all other nodes of a graph. For non-negative weight functions, the Dijkstra algorithm can adapt or to calculate the shortest paths to all nodes of the graph of A * algorithm. For any conservative weight functions of the Bellman - Ford algorithm computes the other hand, always the shortest paths to all other nodes.

Single -destination shortest path

Goal is to determine a shortest path between an end node and all other nodes of the graph here. This problem can be described by a reversal of the edge directions as SSSP.

All- pairs shortest path ( APSP )

In this variant of the problem it comes to the determination of the shortest paths between all pairs of nodes of a graph. Depending on the weight function, it is more efficient to solve for each node one after the SSSP or, however, to use specialized methods, such as the Floyd - Warshall algorithm or the Min- plus- matrix multiplication algorithm, which determine the same for all pairs shortest paths.

Example

In addition to standing given graph is a shortest path between the node and the path, which starts in, and goes after. The path cost is here. But when trying to find a path from to, then the direct route with a cost of not the shortest possible path, as the path of more than just a cost of has.

Formulation as a linear program

In order to determine a shortest path is also can use a linear program. Is interpreted in this case, the path of a flow having a flow value of 1 on the edges of the graph. The determination of the shortest path is then a special case of the minimum -cost flow problem. The corresponding formulation is:

If a - path in the given graph exists, the program has a feasible solution. The program, however, is unlimited if the weight function is not conservative. In this case, the flow can in fact be arbitrarily far along an increased Zykels with negative costs. Otherwise, the problem has an optimal solution, which corresponds to a vector with entries. The amount then describes a shortest - path, the objective function value of the program corresponds to the length of the path.

Node potentials

It turns out that the dualization of the above linear program has an intuitive interpretation. The dual program is given by

A solution of the dual program is called a node potential. It is easily seen that for any solution of the vector also is a solution whereby one can choose arbitrarily. It is usually the value of such that. The objective function is then given by.

If any path between a node and so can the length of the path as estimate follows:

The potential of each node is thus a lower limit for the length of a path. An optimal solution of the dual program can be found if you the potential of a node as the length of the shortest - path is relative to the objective function.

Applications

Algorithms that compute a shortest path, are often used in the calculation of travel routes. For example, the distance between the two cities are calculated. The cities are the nodes of the graph and the edges of roads.

Shortest paths with constraints

A Varallgemeinerung of the problem is obtained if one only - paths considered that obey the additional inequality. It is a further weighting function and a real number.

The resulting Constrained Shortest Path Problem is then NP-hard even for conservative and non-negative objective functions, see.