《算法的乐趣》第二十五节

本节讲带开始时间的拓扑排序：用优先级队列管理同时入度为0的顶点，既按先进先出，又按开始时间小的先出。

本节讲带开始时间的拓扑排序：用优先级队列管理同时入度为0的顶点，既按先进先出，又按开始时间小的先出。算法先让所有入度为0的顶点入队，然后反复出队一个顶点、删除其出边，使相邻顶点入度降为0并入队、按开始时间插位，直到队列为空；若输出顶点数与图顶点数相同则排序成功，否则图中存在环路。按此排序结果与Project软件一致，但需事先手工算好各节点最早开始时间。

随后引入关键路径：工程需用AOE网表示，顶点是事件、带权边是活动，网中只有一个源点和一个汇点。活动的最早开始时间取决于全部前驱结束的时刻，最晚开始时间是在不影响完工的前提下可推迟的上限；两者相等的活动为关键活动，由其构成的最长路径即关键路径。计算时先按拓扑序列正序求各事件最早开始时间，再逆序求最晚开始时间，据此得到每条边（活动）的两个时间，二者相同者即关键活动，按拓扑序输出即为关键路径。