Objectives of the Episode

In this Episode, we learn how to find the shortest path that goes through all vertices in a graph. To do so, we study the traveling salesman problem, that formalizes this objective.

We show that this problem is particularly difficult to solve, i.e., that any algorithm that can solve it has at least a certain complexity. To do this, we introduce the notion of complexity classes, and present the most standard ones.

Articles to study before the Lab

Test your knowledge of this Episode!

Lab instructions

Follow this link for the Lab contents!

Work to do for the next episode

  • Finish the implementation of the program in Lab 5;
  • Study the articles of Episode 6;
  • Be prepared for the 5-minute interview during the next Lab, in which you’ll have to present the work done in Labs 4 and 5.

Important! It is important to be prepared for this interview (see evaluation sheet for details). You should have your programs ready for a demo, and have your codes already open not to lose time searching for them. Having figures ready (if you have some) is already a good way of saving time. Remember that 5 minutes is extremely short.