|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
关键路径:
1)AOE网是一个带有权值的有向图,在AOE网中用点表示事件,边表示时间,起始点称为源点,终点称为汇点,AOE网是从源点开始,结束于汇点。
2)我们需要在AOE网中找到一条从源点到汇点权值之和最大的路径,这就称之为关键路径。
3)etv:顶点Vk最早发生时间
ltv:顶点Vk最晚发生时间
ete:弧最ak早发生时间
lte:弧最晚ak发生时间
4)我们通过比较ete和lte-相邻弧的权,我们可以知道,当且仅当二者相等的时候,该条弧为最大弧,可加入关键路径。重复至找到源点,我们即可找到完整的关键路径
- class EdgeNode
- {
- public:
- int adjvex;
- int weight;
- EdgeNode *next;
- }edgeNode;
- class vertexNode
- {
- public:
- int in;
- int data;
- EdgeNode *fedge;
- };
- class Gra
- {
- public:
- vertexNode *adList;
- int numVertex, numEdge;
- };
- int *ltv, *etv, *stack2;
- int top2;
- void CriticalPath(Gra GL)
- {
- EdgeNode *e;
- int getto;
- int ete, lte;
- // 调用改进后的拓扑排序,求出etv和stack2的值
- TopologicalSort(GL);
- ltv = new int[GL.numVertex];
- for (int i = 0; i < GL.numVertex; i++)
- {
- *(ltv + i) = etv[GL.numVertex-1];
- }
- while (top2 != 0)
- {
- getto = stack2[top2--];
- for (e = GL.adList[getto].fedge; e; e = e->next)
- {
- k = e->adjvex;
- if ((ltv[k] - *e->weight) < ltv[getto])
- {
- ltv[getto] = (ltv[k] - *e->weight);
- }
- }
- }
- for (int j = 0; j < GL.numVertex; j++)
- {
- for (e = GL.adList[j].fedge; e; e = e->next)
- {
- k = e->adjvex;
- ete = etv[j];
- lte = ltv[j] - e->weight;
- if (ete == lte)
- {
- printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight);
- }
- }
- }
- }
复制代码 |
评分
-
查看全部评分
|