The Shortest path problem reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Shortest path problem

In graph theory, the single source shortest path problem is the following: Given a weighted graph, (that is a set N of nodess, a set E of edgess and a real-valued function f : E -> R), and given further two elements n, n' of N, find a path P from n to n', so that

is minimal among all paths connecting n to n'. The all-pairs shortest path problem is a similar problem where we have to find such paths for every two different vertices n to n'.

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* algorithm (or A* pathing algorithm) - a heuristic for single source shortest paths.
• 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.

A related problem is the traveling 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-hard, so there is no known way to solve it in polynomial time.

This is the "Shortest path problem" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.