Edges have Capacities Original flow model is static. Doesnt model time Time required is function of both transit times and capacities Ce is edge capacity("width") At most Ce people can enter edge e=lu, vin one time unit They travel together as a group on e If more than Ce people at U, remainder need to wait to enter e Te is time for one group to traverse edge Start with W people at u How much time does take them all to reach v? C=2
Edges have Capacities • Original Flow Model is static. Doesn’t model time • Time required is function of both transit times and capacities • ce is edge capacity (“width”) • At most ce people can enter edge e=(u,v) in one time unit. They travel together as a group on e • If more than ce people at u, remainder need to wait to enter e • 𝜏e is time for one group to traverse edge • Start with W people at u How much time does take them all to reach v? 13 u v 𝜏=3 c=2
t=0
13 u v 𝜏=3 c=2 t=0
2 C=2
11 u v 𝜏=3 c=2 t=1 2
t=2 9 2 2 C=2
9 u v 𝜏=3 c=2 t=2 2 2
t=3 2 C=2
7 u v 𝜏=3 c=2 t=3 2 2 2