Timeline for Efficiently updating latest finish times via Critical-Path-Method
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2022 at 15:47 | comment | added | prubin♦ | You already have the predecessors and successors of each node stored. You can use a FIFO queue as a "to do" list. On the forward pass, initialize the queue with the first affected node (4 in your diagram). At each step, remove the next node from the queue, update ES/EF for its successors and push any that have changed into the queue. On the reverse pass, initialize the queue with the sink node (assuming it changed) and, when processing each node in the queue, push any predecessors that changed. | |
| May 3, 2022 at 14:04 | vote | accept | Rutger | ||
| May 3, 2022 at 14:04 | comment | added | Rutger | Thank you, all of the points you mention make sense. I'll have to think about how to efficiently use these ideas. That is, I'll need to store somehow which nodes can be skipped since they're on a path from/to a node that is not updated during the forward/backward pass. | |
| May 2, 2022 at 14:43 | history | answered | prubin♦ | CC BY-SA 4.0 |