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.