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.

Answer 2

If there is no upper bound on the number of classes per semester and the dependencies are acyclic, this can be solved by a modified topological sort as follows:

Schedule every class for which all (zero or more) prerequisites are met in the earliest semester in which they are available. Repeat this for all remaining classes (i.e. those not yet scheduled), scheduling them in the earliest semester in which (a) they are available; and (b) all prerequisites have been scheduled in some earlier semester.

This schedules all classes. Call the schedule $S$, and let $C$ be some class. If there is another valid schedule $S'$ which schedules $C$ earlier, then some dependency of $C$ must also be scheduled earlier, or else $S'$ would schedule $C$ invalidly. Chase earlier scheduled dependencies until you reach a class $C_0$ with no dependencies (one such class exists since the dependencies are acyclic). It too must have some dependency which is scheduled earlier in $S'$ than in $S$, but this is impossible since it has no dependencies. Thus no such $S'$ can exist, and $S$ schedules all classes optimally.