php - 根据前任结束日期更新任务开始日期

Question

我想开发一个具有以下算法的程序：

任务 A 和任务 B 是任务 C 的前身。它们都有开始日期和结束日期。如果任务 B 的结束日期延迟，那么任务 C 的开始日期也会延迟。这是最简单的情况。但是，在大多数情况下，图形会越来越复杂。

我应该使用什么算法来更新每个任务的开始日期和结束日期，而不仅仅是递归检查？

谢谢

Answer 1

您需要解决http://en.wikipedia.org/wiki/Longest_path#Acyclic_graphs_and_critical_paths中描述的问题。

在您的程序开始时，进行拓扑排序以建立先行任务在后续任务之前的顺序，并计算出一组初始任务时序。当任务结束日期延迟时，使用拓扑排序的顺序检查该任务的后继者，然后是这些后继者的后继者，依此类推。您可以保留一个尚未检查的可能延迟的继任者列表，以原始顺序从该列表中检查最早的继任者，并在发现必须修改任务的结束日期时插入新的继任者。如果此列表为空，您可以在不检查图表中的所有节点的情况下完成 - 这告诉您没有其他节点受到滑动的影响。