weighted graphs figure cities and distances to find the shortest routeyou list all the possible permutations of cities (bostonseattle-miamiboston-miami-seattlemiami-boston-seattleand so onand calculate the total distance for each permutation the route abceda has total length of the route abcdea is impossible because there is no edge from back to unfortunatelythe number of permutations can be very largeit' the factorial of the number of cities (not counting your home cityif there are cities to visitthere are choices for the first city for the second for the thirdand so ona total of * * * * * or possible routes the problem is impractical to solve for even cities againthere are strategies to reduce the number of sequences that must be checkedbut this helps only little weighted graph is used to implement the problemwith weights representing miles and vertices representing the cities the graph can be non-directed if the distance is the same going from to as from to aas it usually is when driving if the weights represent airfaresthey may be different in different directionsin which case directed graph is used hamiltonian cycles problem that' similar to the tsp but more abstract is that of finding the hamiltonian cycle of graph as we noted earliera cycle is path that starts and ends on the same vertex hamiltonian cycle is one that visits every other vertex in the graph exactly once unlike we did with the tspwe don' care about distancesall we want to know is whether such cycle exists in figure the route abceda is hamiltonian cyclewhile abcdea is not the knight' tour problem is an example of hamiltonian cycle (if you assume the knight returns to its starting squarefinding hamiltonian cycle takes the same ( !time as the tsp you'll see the term exponential time used for big values such as and (which grows even more rapidly than the exponential