I would like to develop a program with the following algorithm in mind:
Task A and Task B are the predecessor of Task C. They all have Start date and End date. If the End date of Task B is delayed, then the Task C Start date will also be delayed. This is the most simple case. However, in most case, the graph will be more and more complex.
What algorithm should I use to update the each task's start date and end date but not only recursively checking?
Thanks
分享 You need to solve the problem described in http://en.wikipedia.org/wiki/Longest_path#Acyclic_graphs_and_critical_paths.
At the start of your program, do a topological sort to establish an order in which predecessor tasks come before successor tasks, and work out an initial set of task timings. When a task end date is delayed, use the order from the topological sort to check the successors of that task, and then the successors of those successors, and so on. You could keep a list of successors not yet checked that may be delayed, checking the earliest from this list in the original order, and inserting new successors if it turns out that a task must have its end date modified. You can finish without checking all nodes in the graph if this list becomes empty - that tells you that no further nodes are affected by the slip.
分享
