《数据结构与算法》——关键路径

luciferzf

关键路径:
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);
                        }
                }
        }
}