Visit all vertices of a graph

Question

I need to find the fastest route passing in all vertices

• Each vertex is a class.
• I can choose the number of classes for semester.
• Some classes have prerequisites (A and B need to be done one semester before C), so I can't do A, B and C at the same time.
• Some classes (C in this case) have only in the second semester of the year (a year has only 2 semester).

So let's say that I study 2 classes each semester

Worst case possible:

First semester of year 1:

• Study A and D

Second semester of year 1:

• Study B (C can't be done because A and B is a prerequisite)

First semester of year 2:

• nothing (C can only be done in the second semester)

Second semester of year 2:

• Study C

The optimal answer would be:

First semester of year 1:

• Study A and B

Second semester of year 1:

• Study C and D

I know the basics of the most common graph algorithm like Kruskall, Prim, DFS... but I just don't know how I could apply them to my problem, the first think that I thought was use Dijkstra algorithm to pass in all vertices but how I would take in count that C can only be done at certain semesters? maybe I should use different algorithms at the same time?

This is not an exercise, it's a real problem that exists at my college, and I would like to solve using a smarter solution using an algorithm rather than a hard coded implementation. Anything that helps me to guide to the right direction will be well appreciated.

Answer 1

Ignoring the even semester constraints, you can model this as a scheduling problem where classes are jobs of processing time $1$ which have to satisfy precedence constraints and must be processed on a parallel machine that can process at most a fixed number $m$ of jobs at the same time. In standard notation, this problem would be called $Pm\mid\text{prec},p_j=1|C_\text{max}$ and is NP-complete (Ullman, NP-complete scheduling problems, J. Comp. Sys. Sci., 10, 1975).

That said, for the size of problems you may be interested in, an integer programming model can likely be solved to optimality. If you let the semesters be $S=\{1,2,\ldots,s\}$, where $s$ is some upper bound on the number of semesters, $m$ the maximum number of classes you can do every semester, and $\prec$ the predecence relation (i.e. $c\prec c'$ if class $c$ must precede class $c'$) a formulation would be \begin{align} \text{minimize } & C_\text{max},\\ \text{subject to } & C_\text{max} \geq s\,x_{cs}, & \forall c,s,\\ & \sum_c x_{cs} \leq m, & \forall s,\\ & \sum_s x_{cs} = 1, & \forall c,\\ & 1+\sum_s s\,x_{cs} \leq \sum_s s\,x_{c's}, & \forall c\prec c'\\ & x_{cs}\in\{0,1\}, & \forall c,s, \end{align} where $x_{cs}=1$ indicates that class $c$ is done in semester $s$. It would be also easy to add even semester restrictions to this model.