Shortest path problem

From Wikipedia, the free encyclopedia

In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. More formally, given a weighted graph (that is, a set V of vertices, a set E of edges, and a real-valued weight function f : E → R), and given further one element v of V, find a path P from v to each v' of V so that

$\sum_{p\in P} f(p)$

is minimal among all paths connecting v to v' . The all-pairs shortest path problem is a similar problem, in which we have to find such paths for every two vertices v to v' .

A solution to the shortest path problem is sometimes called a pathing algorithm. The most important algorithms for solving this problem are:

Dijkstra's algorithm — solves single source problem if all edge weights are greater than or equal to zero. Without worsening the run time, this algorithm can in fact compute the shortest paths from a given start point s to all other nodes.
Bellman-Ford algorithm — solves single source problem if edge weights may be negative.
A* search algorithm solves for single source shortest paths using heuristics to try to speed up the search
Floyd-Warshall algorithm — solves all pairs shortest paths.
Johnson's algorithm — solves all pairs shortest paths, may be faster than Floyd-Warshall on sparse graphs.
Perturbation theory; finds (at worst) the locally shortest path

A related problem is the travelling salesman problem, which is the problem of finding the shortest path that goes through every node exactly once, and returns to the start. That problem is NP-Complete, so an efficient solution is not likely to exist.

Another related problem is the single pair shortest path problem. This can be solved by performing a dijkstra search from each vertex, and terminating the two dijkstras when the search areas overlap.

In a networking or telecommunications mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a widest path problem. e.g.: Shortest (min-delay) widest path or Widest shortest (min-delay) path.

Another application is the games of "six degrees of separation" that try to find the shortest path in graphs like movie stars appearing in the same film.

[edit] References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapters 24: Single-Source Shortest Paths, and 25: All-Pairs Shortest Paths, pp.580–642.

Martin Kroger. Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems, Computer Physics Communications Vol. 168, p. 209, 2005.