FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Shortest path problem

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 A labeled graph with 6 vertices and 7 edges. ... In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ... In mathematics, the set of real numbers, denoted R, is the set of all rational numbers and irrational numbers. ...

sum_{pin 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 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-Complete, so an efficient solution is not likely to exist. Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ... The Bellman-Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ... In computer science, A* (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ... In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshalls algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time. ... Johnsons algorithm is a way to solve the all pairs shortest path problem in a sparse weighted, directed graph. ... In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ... Perturbation theory comprises mathematical methods that are used to find an approximate solution to a problem which cannot be solved exactly, by starting from the exact solution of a related problem. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...


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. For other uses, see Six Degrees (disambiguation). ...

[edit]

References

[edit]

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

  • C code to find the shortest path through a concave polygon
  • Six degrees of Wikipedia, a shortest path query solver for the English Wikipedia.

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m