Related Problems
For shortest path problems in computational geometry, see Euclidean shortest path.
The travelling salesman problem is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. Unlike the shortest path problem, which can be solved in polynomial time in graphs without negative cycles, the travelling salesman problem is NP-complete and, as such, is believed not to be efficiently solvable (see P = NP problem). The problem of finding the longest path in a graph is also NP-complete.
The Canadian traveller problem and the stochastic shortest path problem are generalizations where either the graph isn't completely known to the mover, changes over time, or where actions (traversals) are probabilistic.
The shortest multiple disconnected path is a representation of the primitive path network within the framework of Reptation theory.
The problems of recalculation of shortest paths arises if some graph transformations (e.g., shrinkage of nodes) are made with a graph.
The widest path problem seeks a path so that the minimum label of any edge is as large as possible.
Read more about this topic: Shortest Path Problem
Famous quotes containing the words related and/or problems:
“The question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)
“If combat means living in a ditch, females have biological problems staying in a ditch for 30 days because they get infections.... Males are biologically driven to go out and hunt giraffes.”
—Newt Gingrich (b. 1943)