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:
“Generally there is no consistent evidence of significant differences in school achievement between children of working and nonworking mothers, but differences that do appear are often related to maternal satisfaction with her chosen role, and the quality of substitute care.”
—Ruth E. Zambrana, U.S. researcher, M. Hurst, and R.L. Hite. “The Working Mother in Contemporary Perspectives: A Review of Literature,” Pediatrics (December 1979)
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)