AOE網(wǎng)：在一個(gè)表示工程的帶權(quán)有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間，稱這樣的有向圖叫做邊表示活動(dòng)的網(wǎng)，簡(jiǎn)稱AOE網(wǎng)。AOE網(wǎng)中沒(méi)有入邊的頂點(diǎn)稱為始點(diǎn)（或源點(diǎn)），沒(méi)有出邊的頂點(diǎn)稱為終點(diǎn)（或匯點(diǎn)）。

AOE網(wǎng)的性質(zhì)：

⑴ 只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各活動(dòng)才能開(kāi)始；

⑵ 只有在進(jìn)入某頂點(diǎn)的各活動(dòng)都結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。

關(guān)鍵路徑：在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)具有最大路徑長(zhǎng)度（該路徑上的各個(gè)活動(dòng)所持續(xù)的時(shí)間之和）的路徑稱為關(guān)鍵路徑。

關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)：e[i]=l[i]的活動(dòng)

　　由于AOE網(wǎng)中的某些活動(dòng)能夠同時(shí)進(jìn)行，故完成整個(gè)工程所必須花費(fèi)的時(shí)間應(yīng)該為始點(diǎn)到終點(diǎn)的最大路徑長(zhǎng)度。關(guān)鍵路徑長(zhǎng)度是整個(gè)工程所需的最短工期。

與關(guān)鍵活動(dòng)有關(guān)的量：

⑴ 事件的最早發(fā)生時(shí)間ve[k]

　　ve[k]是指從始點(diǎn)開(kāi)始到頂點(diǎn)vk的最大路徑長(zhǎng)度。這個(gè)長(zhǎng)度決定了所有從頂點(diǎn)vk發(fā)出的活動(dòng)能夠開(kāi)工的最早時(shí)間。

⑵ 事件的最遲發(fā)生時(shí)間vl[k]

　　vl[k]是指在不推遲整個(gè)工期的前提下,事件vk允許的最晚發(fā)生時(shí)間。

⑶ 活動(dòng)的最早開(kāi)始時(shí)間e[i]

　　若活動(dòng)ai是由弧<vk , vj>表示，則活動(dòng)ai的最早開(kāi)始時(shí)間應(yīng)等于事件vk的最早發(fā)生時(shí)間。因此，有：e[i]=ve[k]

⑷ 活動(dòng)的最晚開(kāi)始時(shí)間l[i]

　　活動(dòng)ai的最晚開(kāi)始時(shí)間是指，在不推遲整個(gè)工期的前提下， ai必須開(kāi)始的最晚時(shí)間。若ai由弧<vk，vj>表示，則ai的最晚開(kāi)始時(shí)間要保證事件vj的最遲發(fā)生時(shí)間不拖后。因此，有：l[i]=vl[j]-len<vk, vj>

示例：

所以：

//關(guān)鍵路徑，不是有向無(wú)環(huán)圖返回-1，否則返回關(guān)鍵路徑長(zhǎng)度//拓?fù)湫蛄衧tack<int> topOrder;//拓?fù)渑判颍槺闱髒e數(shù)組bool topologicalSort(){	queue<int> q;	for (int i = 0; i < n; i++)	{		if (inDegree[i] == 0)		{			q.push(i);		}	}	while (!q.empty())	{		int u = q.front();		q.pop();		topOrder.push(u);//將u加入拓?fù)湫蛄?	for (int i = 0; i < G[u].size(); i++)		{			int v = G[u][i].v;//u的i號(hào)后繼結(jié)點(diǎn)編號(hào)為v			inDegree[v]--;			if (inDegree[v] == 0)			{				q.push(v);			}			//用ve[u]來(lái)更新u的所有后繼結(jié)點(diǎn)v			if (ve[u] + G[u][i].w > ve[v])			{				ve[v] = ve[u] + G[u][i].w;			}		}	}	if (topOrder.size() == n)return true;	else return false;}//關(guān)鍵路徑，不是有向無(wú)環(huán)圖返回-1，否則返回關(guān)鍵路徑長(zhǎng)度int CriticalPath(){	memset(ve, 0, sizeof(ve));//ve數(shù)組初始化	if (topologicalSort() == false)	{		return -1;//不是有向無(wú)環(huán)圖，返回-1	}	fill(vl, vl + n, ve[n - 1]);//vl數(shù)組初始化，初始值為匯點(diǎn)的ve值	//直接使用topOrder出棧即為逆拓?fù)湫蛄校蠼鈜l數(shù)組	while (!topOrder.empty())	{		int u = topOrder.top();//棧頂元素為u		topOrder.pop();		for (int i = 0; i < G[u].size(); i++)		{			int v = G[u][i].v;//u的后繼結(jié)點(diǎn)			//用u的所有后繼結(jié)點(diǎn)v的vl值來(lái)更新vl[u]			if (vl[v] - G[u][i].w < vl[u])			{				vl[u] = vl[v] - G[u][i].w;			}		}	}	//遍歷鄰接表的所有邊，計(jì)算活動(dòng)的最早開(kāi)始時(shí)間e和最遲開(kāi)始時(shí)間l	for (int u = 0; u < n; u++)	{		for (int i = 0; i < G[u].size(); i++)		{			int v = G[u][i].v, w = G[u][i].w;			//活動(dòng)的最早開(kāi)始時(shí)間e和最遲開(kāi)始時(shí)間l			int e = ve[u], l = vl[v] - w;			//如果e==l,說(shuō)明u->v是關(guān)鍵活動(dòng)			if (e == l)			{				PRintf("%d->%d/n", u, v);//輸出關(guān)鍵活動(dòng)			}		}	}	return ve[n - 1];//返回關(guān)鍵路徑長(zhǎng)度}/*若事先不知道匯點(diǎn)編號(hào)，可以取ve數(shù)組的最大值：int maxLength = 0;for(int i=0;i<n;i++){	if(ve[i]>maxLength)	{		maxLength = ve[i];	}}fill(vl,vl+n,maxLength);若有多條關(guān)鍵路徑，可以類比最短路徑中保存前驅(qū)結(jié)點(diǎn)的做法，新建一個(gè)鄰接表來(lái)保存所有的關(guān)鍵活動(dòng)*/