Shortest path

In graph theory, a shortest path is a path between two different nodes of a graph which has a minimum length with respect to an edge weight function . If the edges in the graph all have the weight 1, that is for all edges , then the shortest path is a - -path with the smallest possible number of edges between and . ${\displaystyle s,t\in V}$ ${\displaystyle c\colon E\to \mathbb {R} }$ ${\displaystyle c(e)=1}$ ${\displaystyle e\in E}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$

In the literature, the problem is often referred to as the Shortest Path Problem .

complexity

The complexity depends largely on the type of weight function and on whether paths or edge trains are being considered. In edge trains, nodes and edges can be repeated, while paths do not use any nodes twice. There are three types of weight functions:

• Weight functions without negative weights;
• Conservative weight function: A weight function is said to be conservative for the graph if for all cycles of ; ${\displaystyle G}$ ${\displaystyle c(C)=\sum _{e\in C}c(e)\geq 0}$ ${\displaystyle C}$ ${\displaystyle G}$
• Weight functions with any weights.

The exact formulation of the problem is crucial in order to be able to answer the question of complexity.

Without negative weights

With Dijkstra's algorithm the problem can be solved in a running time of , where denotes the number of edges and the number of nodes in the graph. Note that the shortest paths are also the shortest edges. If all weights are genuinely positive, then the shortest paths match the shortest edges. ${\displaystyle O(m+n\cdot \log(n))}$ ${\displaystyle m}$ ${\displaystyle n}$

With any weight and with edges

If the graph contains a cycle in which the sum over the weights is strictly negative, then there are nodes that do not have a shortest line of edges. If there is an edge from to this cycle and an edge from this cycle to , then you can create an arbitrarily short edge from to by running through the cycle only sufficiently often. The Bellman-Ford algorithm can find a shortest edge train (if it exists) in a running time of or prove that it does not exist by finding a negative cycle. The decision problem as to whether there is a path of length can thus be solved in polynomial time. ${\displaystyle s,t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle O(nm)}$ ${\displaystyle \leq C}$

With arbitrary weights and with paths

This variant of the problem is NP- hard. This can be proven, for example, by a reduction of the NP-heavy Hamiltonian path problem by setting all weights to −1 in the shortest path problem. Note that this construction contains negative cycles, and therefore the NP severity does not hold for conservative weight functions.

Conservative weight function and with paths

The Bellman-Ford algorithm can find a shortest path in a running time of . ${\displaystyle O(nm)}$

The literature is mostly limited to non-negative weights or conservative weight function. With one of these additional requirements, every shortest path is automatically a shortest line of edges and that is why this distinction is often not made in the literature.

In contrast to the shortest path problem, the longest path problem is NP-hard even for unweighted graphs .

Variations of the problem

Aside from determining a shortest - path, there are a few other, but very similar problems: ${\displaystyle s}$ ${\displaystyle t}$

Single-source shortest path (SSSP)

This variant of the shortest paths problem deals with the problem of how to compute the shortest paths between a given starting node and all other nodes of a graph. For nonnegative weight functions, the Dijkstra algorithm or the A * algorithm can be adapted in order to calculate the shortest paths to all nodes of the graph. On the other hand, the Bellman-Ford algorithm always calculates the shortest paths to all other nodes for any conservative weight functions.

Single-destination shortest path (SDSP)

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

All-pairs shortest path (APSP)

This variant of the problem is about determining the shortest paths between all pairs of nodes in a graph. Depending on the weight function, it is more efficient to solve the SSSP for each node one after the other or to use specialized methods such as the Floyd-Warshall algorithm or the min-plus matrix multiplication algorithm , which determine the shortest paths for all pairs at the same time.

example

Sample graph

In the graph on the right there is a shortest path between the nodes and the path that starts in and goes over to . The path costs are here . However, if you want to find a path from to , the direct path with costs from is not the shortest possible path, since the path from via to only has costs from . ${\displaystyle D}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle 9+8=17}$ ${\displaystyle D}$ ${\displaystyle E}$ ${\displaystyle 15}$ ${\displaystyle D}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle 14=8+6}$

Formulation as a linear program

A linear program can also be used to determine a shortest path . In this case, the path is interpreted as a flow with a flow value of 1 on the edges of the graph. The determination of the shortest path is then a special case of the min-cost-flow problem. The corresponding formulation is:

${\displaystyle {\begin{aligned}\min &\sum _{e\in E}c_{e}x_{e}\\{\text{so dass }}&\forall \;v\in V\colon \;\sum _{e\in \operatorname {\delta ^{-}} (v)}x_{e}-\sum _{e\in \operatorname {\delta ^{+}} (v)}x_{e}={\begin{cases}-1,&{\text{falls }}v=s\\1,&{\text{falls }}v=t\\0,&{\text{sonst }}\end{cases}}\\&\forall \;e\in E\colon \;x_{e}\geq 0\\\end{aligned}}}$

If there is a - path in the given graph, then the program has a feasible solution. However, the program is unlimited if the weight function is not conservative. In this case, the flow can be increased arbitrarily along a cycle with negative costs. Otherwise the problem has an optimal solution which corresponds to a vector with entries. The set then describes a shortest - path, the objective function value of the program corresponds to the length of the path. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle x}$ ${\displaystyle 0/1}$ ${\displaystyle |E|}$ ${\displaystyle \{e\in E\,:\,x_{e}=1\}}$ ${\displaystyle s}$ ${\displaystyle t}$

Node potentials

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

${\displaystyle {\begin{aligned}\max {}&y_{t}-y_{s}\\{\text{so dass }}&\forall \;e=(u,v)\in E\colon \;y_{v}-y_{u}\leq c_{e}\;\;\end{aligned}}}$

A solution to the dual program is called a node potential . It is easy to see that the vector is also a solution for every solution , and one can choose at will. As a rule, the value of is set so that . The objective function is then given by . ${\displaystyle y}$ ${\displaystyle (y_{v})_{v\in V}}$ ${\displaystyle (y_{v}+\delta )_{v\in V}}$ ${\displaystyle \delta \in \mathbb {R} }$ ${\displaystyle \delta }$ ${\displaystyle y_{s}=0}$ ${\displaystyle \max \;y_{t}}$

If there is any path between and a node , the length of the path can be estimated as follows: ${\displaystyle P}$ ${\displaystyle s}$ ${\displaystyle w\neq s}$

${\displaystyle c(P)=\sum _{e\in P}c_{e}\geq \sum _{e=(u,v)\in P}y_{v}-y_{u}=y_{w}}$

The potential of each node is therefore a lower bound for the length of a path. An optimal solution of the dual program can be found if one sets the potential of a node as the length of the shortest - path with respect to the objective function . ${\displaystyle w\neq s}$ ${\displaystyle s}$ ${\displaystyle w}$ ${\displaystyle c}$

Applications

See also : pathfinding

Algorithms that calculate a shortest path are often used in the calculation of travel routes. For example, the distance between two cities can be calculated. The cities are the nodes of the graph and the streets are the edges. Various algorithms are in the free Python - Library NetworkX implemented.

Shortest routes with constraints

A generalization of the problem is obtained if one only considers - paths which obey the additional inequality . There is another weight function and a real number. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle P}$ ${\displaystyle \sum _{e\in P}u_{e}\leq U}$ ${\displaystyle u\colon E\to \mathbb {R} _{+}}$ ${\displaystyle U}$

The resulting constrained shortest path problem is then also NP-difficult for conservative or nonnegative objective functions, see HC Joksch (1966).

literature

• Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms . 2nd Edition. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7 .
• Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . 2nd Edition. 2007. ISBN 978-3-486-58262-8
• HC Joksch (1966). The shortest route problem with constraints . J. Math. Anal. Appl. 14, pages 191-197

Individual evidence

1. ^ Bernhard Korte , Jens Vygen : Combinatorial Optimization. Theory and Algorithms. 4th edition. Springer, Berlin et al. 2008, ISBN 978-3-540-71844-4 ( Algorithms and Combinatorics 21)
2. ^ Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Retrieved October 24, 2018 . 
3. ↑ HC Joksch (1966)