《数据结构与算法》——关键路径
关键路径: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;
for (int i = 0; i < GL.numVertex; i++)
{
*(ltv + i) = etv;
}
while (top2 != 0)
{
getto = stack2;
for (e = GL.adList.fedge; e; e = e->next)
{
k = e->adjvex;
if ((ltv - *e->weight) < ltv)
{
ltv = (ltv - *e->weight);
}
}
}
for (int j = 0; j < GL.numVertex; j++)
{
for (e = GL.adList.fedge; e; e = e->next)
{
k = e->adjvex;
ete = etv;
lte = ltv - e->weight;
if (ete == lte)
{
printf("<v%d,v%d> length: %d , ", GL->adjList.data, GL->adjList.data, e->weight);
}
}
}
}
页:
[1]