MathCastle
Graph TheoryMediumGraph Algorithms

Graph Algorithms · Medium problem

A project has tasks s,r,t,u,v,w,xs,r,t,u,v,w,x with durations (days) and prerequisites s→rs \to r (33), s→ts \to t (22), r→ur \to u (44), t→ut \to u (55), t→vt \to v (22), u→wu \to w (33), v→wv \to w (22), t→xt \to x (11), x→wx \to w (22). Each number is how many days that task itself takes, and the project (ending at ww) finishes in 1010 days at the earliest. By how many days could task xx's completion be delayed from its earliest possible finish without delaying the whole project (that is, what is xx's slack)?