|
|
|
|
|
Shortest Path ProblemIn 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 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, in which we have to find such paths for every two 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: 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 an efficient solution is not likely to exist.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|