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 content of a thought depends on its external relations; on the way that the thought is related to the world, not on the way that it is related to other thoughts.”
—Jerry Alan Fodor (b. 1935)
“I had many problems in my conduct of the office being contrasted with President Kennedy’s conduct in the office, with my manner of dealing with things and his manner, with my accent and his accent, with my background and his background. He was a great public hero, and anything I did that someone didn’t approve of, they would always feel that President Kennedy wouldn’t have done that.”
—Lyndon Baines Johnson (1908–1973)