0
$\begingroup$

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ I don't understand what you're asking. What does the graph actually mean? How are the prerequisite constraints represented and why aren't they shown in the graph? $\endgroup$ – David Richerby Oct 12 '18 at 23:11
  • $\begingroup$ As your constraints are directional (e.g. "A and B need to be done before C"), you should be thinking in terms of a directed graph, probably either a dependency graph or a DAG of some sort depending on what precisely you're modelling (so you need to figure that out too). Also, it's "Dijkstra", not "Djakarta" :D $\endgroup$ – Luke Mathieson Oct 12 '18 at 23:45
  • $\begingroup$ @DavidRicherby sorry if it wasn't clear. I don't exactly know how to represent the problem in the graph. There are 2 rules that it needs to be fulfill to be a valid path. Certain classes have prerequisite classes which I tried to represent in the graph so that the only way to get in C was by visiting A and B, and the second rule is that C can only be visit in the second semester of the year but I have no idea how put that in the graph. $\endgroup$ – fajuchem Oct 12 '18 at 23:53
  • $\begingroup$ @LukeMathieson Thanks for the response, I was already thinking as a directional but I end up not drawing the arrows in the graph, that solves the prerequisite of a class, but not the part that C can only be visited in the second semester. So let's say that each time that I move is a cycle and each cycle I can visit 3 vertices but C can only be visited at pair cycles. $\endgroup$ – fajuchem Oct 13 '18 at 0:05
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.