Encyclopedia > Shortest path problem

  Article Content

Shortest path problem

The shortest path problem in graph theory is the following: Given a weighted graph, (that is a set N of nodes, a set E of edges 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

   ∑ f(p)
 p ∈ P
or

 -----
  \
  /      f(p)
 -----
 p in P

is minimal among all paths connecting n to n'.

A solution to the shortest path problem is sometimes called a "pathing algorithm". The most important algorithm for solving this problem in case all edge weights are greater than or equal to zero is Dijkstra's algorithm. Without worsening the run time, this algorithm can in fact compute the shortest paths from a given start point s to all other nodes. Another algorithm is the A* algorithm[?] (or A* pathing algorithm[?].)

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
W.B. Yeats

...     Contents William Butler YeatsRedirected from W.B. Yeats William Butler Yeats (June 13, 1865 - January 28, 1939) (also often referred to as W.B. ...