body, table{font-family: 微软雅黑; font-size: 13.5pt}
table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;}
th{border: 1px solid gray; padding: 4px; background-color: #DDD;}
td{border: 1px solid gray; padding: 4px;}
tr:nth-child(2n){background-color: #f8f8f8;}
AOE网(Activity On Edge NetWword):
在表示一个工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网(Activity On Edge NetWword)。
AOE网中没有入边的顶点称为始点（源点），没有出边的顶点称为终点（汇点）。
AOV & AOE
AOE网是顶点表示活动的网，只描述活动之间的制约关系；AOE网是用边表示活动的网，边上的权值表示活动持续的时间。
关键路径：
我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
| 1、事件的最早发生时间etv(earliest time of vertex)：即顶点Vk的最早发生时间。 这个最大路径也相当于从始点到指定顶点Vk的最大路径长度。有etv[0]=0 etv[k]=max{etv[j]+len<Vj,Vk>} 2、事件的最晚发生时间ltv(latest time of vertex)：即顶点Vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。 ltv[Vk]是指在不推迟整个工期的前提下，事件Vk允许的最晚发生时间。 ltv[Vn]=ve[Vn],Vn为图中最后一个顶点 ltv[Vk]=min{ltv[j]-len<Vk,j>} | 3、活动的最早开工时间ete(earliest time of edge)：即弧ak的最早发生时间。 若活动ai是由弧<Vk,Vj>表示，则活动ai的最早开始时间应等于事件Vk的最早发生时间。有：ete[i]=etv[k]。 4、活动的最晚开工时间lte(latest time of edge)：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。 若活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开始的最晚时间。若ai由弧<Vk,Vj>表示，则ai的最晚开始时间要保证事件Vj的最迟发生时间不拖后。有：lte[i]=ltv[j]-<Vk,Vj> | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
初始etv全部为0，ltv为tev[9]
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 关键活动：ete = lte a1 → a4 → a6 → a8 → a11 → a12 算法要首先确定有向图是不是AOV图，在确定的过程中要保存拓扑排序的顺序，最后初始化ltv数组要用到 |
| /* AOE.h */ #ifndef __AOE_H__ #define __AOE_H__ #include"Graph.h" #include<iostream> #include<stack> namespace meihao { //边表结点 typedef struct EdgeNode { int vertexIdx; //邻接点域，存放该结点在顶点表数组中的下标 int weight; //存放对应顶点到该边表结点的边上的权值 struct EdgeNode* next; //存放下一个边表结点的位置 }edgeNode,*pEdgeNode; //顶点表结点 typedef struct VertexNode { int in; //顶点入度 int data; //顶点与，存放顶点数据信息 edgeNode* firstEdge; }vertexNode,*pVertexNode; void initDataStruct(const meihao::Graph& g,vertexNode*& vertexArr); //根据图来初始化出我们要的顶点数组和对应的边表 int TopologicalSort_AOV(const meihao::Graph& g,vertexNode*& vertexArr,int* elv,stack<int>& AOV); //成功返回0，失败返回-1 //在这个过程中计算出elv,并保存这个拓扑排序的逆序 //这个拓扑排序的逆序后面求关键路径要用来计算ltv void CriticalPath_AOE(const meihao::Graph& g); }; #endif /* data.txt */ 10 0 1 2 3 4 5 6 7 8 9 0 3 4 0 0 0 0 0 0 0 0 0 0 5 6 0 0 0 0 0 0 0 0 8 0 7 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 9 4 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 /* testmain.cpp */ #include"Graph.h" #include"AOE.h" #include<iostream> using namespace std; int main() { meihao::Graph g("data.txt"); meihao::CriticalPath_AOE(g); system("pause"); } | /* AOE.cpp */ #include"AOE.h" namespace meihao { void initDataStruct(const meihao::Graph& g,vertexNode*& vertexArr) { int vertexNum = g.getGraphVertexNumber(); vertexArr = new VertexNode[vertexNum](); //顶点数组开辟空间 for(int idx=0;idx!=vertexNum;++idx) { vertexArr[idx].data = idx; vertexArr[idx].in = g.getInputDegree(idx); //获取入度 vertexArr[idx].firstEdge = nullptr; } for(int idx=0;idx!=vertexNum;++idx) { for(int iidx=0;iidx!=vertexNum;++iidx) { if(0!=g.getGraphEdgeWeight(idx,iidx)) { edgeNode* tmp = new edgeNode(); tmp->vertexIdx = iidx; tmp->weight = g.getGraphEdgeWeight(idx,iidx); tmp->next = vertexArr[idx].firstEdge; vertexArr[idx].firstEdge = tmp; } } } } int TopologicalSort_AOV(const meihao::Graph& g,vertexNode*& vertexArr,int* etv,stack<int>& AOV) { if(!AOV.empty()) return -1; //传递来的AOV必须是空的 stack<int> zeroInputDegreeVertex; int vertexNum = g.getGraphVertexNumber(); vertexArr = nullptr; initDataStruct(g,vertexArr); //入度为0的顶点入栈 for(int idx=0;idx!=vertexNum;++idx) { if(0==vertexArr[idx].in) zeroInputDegreeVertex.push(idx); } //初始化elv,每个顶点的最早开始时间,全部为0 for(int idx=0;idx!=vertexNum;++idx) { etv[idx] = 0; } //遍历输出拓扑排序 int cnt = 0; cout<<"拓扑排序："; while(!zeroInputDegreeVertex.empty()) { int idx = zeroInputDegreeVertex.top(); cout<<vertexArr[idx].data<<" "; //输出一个度为0的顶点 zeroInputDegreeVertex.pop(); AOV.push(idx); //保存结果 ++cnt; for(edgeNode* node = vertexArr[idx].firstEdge;nullptr!=node;node=node->next) { if( (etv[idx]+node->weight) > etv[node->vertexIdx] ) { //从第一个入度为0的点，也就是源点，就可以开始计算从源点出发可以到达的点的elv了 etv[node->vertexIdx] = etv[idx]+node->weight; } --(vertexArr[node->vertexIdx].in); if(0==vertexArr[node->vertexIdx].in) zeroInputDegreeVertex.push(node->vertexIdx); //这里比较特殊，node->vertexIdx == vertexArr[node->vertexIdx].data } } cout<<endl; if(cnt==vertexNum) return 0; else return -1; } void CriticalPath_AOE(const meihao::Graph& g) { int vertexNum = g.getGraphVertexNumber(); stack<int> AOV; int* etv = new int[vertexNum]; //顶点表示的事件的最早开始时间数组 vertexNode* vertexArr = nullptr; int ret = TopologicalSort_AOV(g,vertexArr,etv,AOV); if(-1==ret) { cout<<"TopologicalSort_AOV error!"<<endl; return ; } //根据得到的AOE网的拓扑排序的逆序求ltv, 顶点表示的事件的最晚开始时间数组 int* ltv = new int[vertexNum]; for(int idx=0;idx!=vertexNum;++idx) { ltv[idx] = etv[vertexNum-1]; } while(!AOV.empty()) { int vertexIdx = AOV.top(); for(edgeNode* node = vertexArr[vertexIdx].firstEdge;nullptr!=node;node=node->next) { if( ltv[vertexIdx] > ltv[node->vertexIdx]-node->weight ) ltv[vertexIdx] = ltv[node->vertexIdx]-node->weight; } AOV.pop(); } /* test etv 和 ltv */ cout<<"etv"<<" "; for(int idx=0;idx!=vertexNum;++idx) { cout<<etv[idx]<<" "; } cout<<endl; cout<<"ltv"<<" "; for(int idx=0;idx!=vertexNum;++idx) { cout<<ltv[idx]<<" "; } cout<<endl; //现在已经得到了etv和ltv了，可以遍历图中所有顶点，根据etv和ltv求出对应顶点之间的活动的ete和lte cout<<"关键路径："; for(int idx=0;idx!=vertexNum;++idx) {//从0号顶点开始，判断0号可以到达其他顶点之间的活动 for(edgeNode* node=vertexArr[idx].firstEdge;nullptr!=node;node=node->next) { //ete 活动最早开始时间，<idx,node,vertexIdx>, ete = etv[idx] int ete = etv[idx]; //lte 活动最晚开始时间，<idx,node,vertexIdx>, lte = ltv[node->vertexIdx] - <idx,node,vertexIdx> int lte = ltv[node->vertexIdx] - node->weight; if(ete==lte) //相等，关键路径，关键活动 { cout<<"<"<<idx<<","<<node->vertexIdx<<">="<<g.getGraphEdgeWeight(idx,node->vertexIdx)<<" "; } } } cout<<endl; } }; //最后记得释放动态开辟的内存空间 |