有向无环图任务调度算法
DAG ----- 图论中,如果有向图中任意一个顶点从该点出发经过任意边都无法回到该点,那么这个图称为有向无环图。
DAG常常用于多个任务的调度,各个任务之间可能存在依赖关系。
所以一个工程划分为不同的任务, 有开始任务和结束任务,通过合理规划执行小任务的顺序,确保总工期最短。
在DAG中,顶点表示事件,顶点之间的连线表示活动,权值表示时间。
设x为源点,y为汇点,v为其中一个事件,
v最早可发生时间ve(v)即x到v的最长路径。
vl(v)即v最晚发生时间即ve(y)- max(vy)
当ve(v) = vl(v) ,v为关键路径。