The Routing Problem
The Routing Problem
Given a graph, perhaps derived from a map of roads or walkways, a natural problem is to find the shortest cycle in the graph that visits all vertices. This is called the routing problem. A closely related problem is to find the shortest Hamiltonian cycle, where the path visits all vertices but does not repeat any edges. These two problems sound identical, but they are not, since it can happen that backtracking along an edge can lead to a shorter overall route. All distances here are Euclidean distances; the blue cycle is the shortest Hamiltonian tour, and the yellow cycle is the shortest solution to the routing problem.