Traveling salesman problem tried to find the shortest path through an undirected graph traversing every vertex, for example, user, John, wants to drive to every other user minimizing the total distance driven. As the number of vertices and edges increase, the number of permutations also increases polynomially to cover all the possible paths from vertex to vertex. The time complexity increases polynomially to a point that the problem can take a very long time to solve. Rather than solve it completely and accurately, an approach known as a greedy algorithm is used to solve the problem as optimally as possible.

To solve the traveling salesman problem, the greedy approach is to quickly choose the shortest edge, knowing that this could be a nonoptimal selection if we traverse further depth-wise.

A diagram of the greedy algorithm on the graph of users and friends is as follows, where we see the traversal picking the shortest weighted edge at each vertex. Also note that the vertices Larry (7) and Liz (4) are never visited: