B 宽度优先（种子染色法） 5．关键路径几个定义：顶点1为源点，n为汇点。a. 顶点事件最早发生时-学而优知识库

B 宽度优先（种子染色法） 5．关键路径几个定义：顶点1为源点，n为汇点。a. 顶点事件最早发生时

B 宽度优先（种子染色法）
5．关键路径
几个定义：顶点1为源点，n为汇点。
a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 边活动最早开始时间 Ee[I], 若边I由表示，则Ee[I] = Ve[j];
d. 边活动最晚开始时间 El[I], 若边I由表示，则El[I] = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。
求解方法：
a. 从源点起topsort,判断是否有回路并计算Ve;

参考答案

查看答案