Time Complexity
Nearest Neighbour runs in O(N²). 2-opt adds O(N²) per pass. Held–Karp is exact but exponential: O(2N·N²), feasible only for small N.
How GiTrip Optimises Routes
GiTrip uses different algorithms depending on the number of stops. Explore each approach step by step below using London landmarks.
Trade-offs
The NN greedy approach can produce paths up to 25% longer than optimal. Adding 2-opt iteratively reverses sub-segments to shorten the route. Held–Karp guarantees the shortest path but is too slow for many stops.
When GiTrip Uses Each
For 12 or fewer stops GiTrip uses Held–Karp for the exact optimum. For more than 12 it falls back to Nearest Neighbour + 2-opt, trading optimality for speed. Try each tab to compare.