graph-theorydirected-acyclic-graphstopological-sort

How to find bottleneck in directed graph


Let's say we have a directed graph that represents school courses. Some courses are a prerequisite of others (e.g. [2,1] means that course 1 needs to be taken before course 2). We can take as many courses in parallel as we want, as long as the prerequisite is completed

I think this would naturally fit into a directed graph. To get the order of courses that can be taken, we would use topological sorting. If instead, we want to find the "bottleneck" course, what kind of algorithm makes sense?

A bottleneck looks like this:

Visualization attached below in case it helps

enter image description here

I'm not sure where to start with this problem


Solution

  • You seem to be assuming that

    1. Every course MUST be taken
    2. Every course takes the same amount of time

    Algorithm: