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:
“Becoming responsible adults is no longer a matter of whether children hang up their pajamas or put dirty towels in the hamper, but whether they care about themselves and others—and whether they see everyday chores as related to how we treat this planet.”
—Eda Le Shan (20th century)
“There are nowadays professors of philosophy, but not philosophers. Yet it is admirable to profess because it was once admirable to live. To be a philosopher is not merely to have subtle thoughts, nor even to found a school, but so to love wisdom as to live according to its dictates, a life of simplicity, independence, magnanimity, and trust. It is to solve some of the problems of life, not only theoretically, but practically.”
—Henry David Thoreau (1817–1862)