激情情色五月天,久久久久黄色

定義

如果我們要獲得一個流程圖完成的最短時間，就必須要分析它們之間的拓撲關(guān)系，并且找到當中最關(guān)鍵的流程，這個流程的時間就是最短時間。所以，圖的關(guān)鍵路徑一般可用于解決工程完成需要的最短時間。

在一個表示工程的帶權(quán)值有向圖中，用頂點表示事件，用弧表示活動，用弧上的權(quán)值表示活動的持續(xù)時間，這種有向圖被我們稱為AOE網(wǎng)(Activity On Edge Network)。我們把AOE網(wǎng)中入度為0的頂點稱為源點，出度為0的頂點稱之為終點。正常情況下，AOE網(wǎng)只有一個源點，一個終點。

AOE網(wǎng)和AOV網(wǎng)的區(qū)別是，AOE網(wǎng)的權(quán)值表示活動持續(xù)的時間，AOV網(wǎng)的邊表示活動之間的制約關(guān)系。二者的區(qū)別如下圖：

aov&aoe.png

我們把路徑上各個活動所持續(xù)的時間之和稱為路徑長度，從源點到終點具有最大長度的路徑叫做關(guān)鍵路徑，在關(guān)鍵路徑上的活動稱為關(guān)鍵活動。如上圖所示，開始->發(fā)動機完成->部件集中到位->組裝完成就是關(guān)鍵路徑，路徑長度為5.5。

關(guān)鍵路徑算法原理

我們只需要找到所有活動的最早開始時間和最晚開始時間，并且比較他們，如果相等就意味著此活動是關(guān)鍵活動，活動的路徑為關(guān)鍵路徑，如果不等則不是。所以，我們需要以下輔助參數(shù)：

事件的最早發(fā)生時間etv(earliest time of vertex)，即頂點 $v_k$ 的最早發(fā)生時間
事件的最晚發(fā)生時間ltv(latest time of vertex)，即頂點 $v_k$ 的最晚發(fā)生時間，超出此時間將會延誤整個工期
活動的最早開始時間ete(earliest time of edge)，即弧 $a_k$ 最早發(fā)生時間
活動的最晚開始時間lte(latest time of edge)，即弧 $a_k$ 最晚發(fā)生時間，超出此時間將會延誤整個工期

我們由etv和ltv可以求出ete、lte，然后根據(jù)ete[k]和lte[k]來判斷弧 $a_k$ 是否是關(guān)鍵活動。求時間的最早發(fā)生時間etv的過程，就是我們從頭至尾找拓撲序列的過程。因此在求關(guān)鍵路徑之前，需要先調(diào)用一次拓撲排序來計算etv。下面我們通過一個示例來看看關(guān)鍵路徑的計算：

aoce示例.png

首先，實現(xiàn)圖的結(jié)構(gòu)：

#define T_MAX_SIZE 100
#define T_ERROR -1
#define T_OK 1
#define MAX_VEX_COUNT 100
#define INT_INFINITY 65535
typedef int TStatus;
// 頂點類型
typedef int VertexType;
// 權(quán)值類型
typedef int EdgeType;

typedef struct EdgeNode {
    // 鄰接點域 存儲鄰接點對應(yīng)的頂點下標
    int adjvex;
    // 權(quán)值
    int weight;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    VertexType data;
    // 指向邊表的第一個結(jié)點
    EdgeNode *firstEdge;
    // 入度
    int inDegree;
} VertexNode, AdjList[MAX_VEX_COUNT];

typedef struct {
    // 頂點數(shù)組
    AdjList adjList;
    int vertexNum, edgeNum;
} AdjListGraph;

typedef struct {
    // 起點下標 終點下標 權(quán)值
    int startIndex, endIndex, weight;
} EdgeInfo;

void initEdgeInfos(int edgesNum, int starts[], int ends[], int weights[], EdgeInfo edges[]) {
    for (int i = 0; i < edgesNum; i++) {
        EdgeInfo *eInfo = (EdgeInfo *)malloc(sizeof(EdgeInfo));
        eInfo->startIndex = starts[i];
        eInfo->endIndex = ends[i];
        eInfo->weight = weights[i];
        edges[i] = *eInfo;
    }
}

void initAdjListGraph(AdjListGraph *graph, int vertexNum, int edageNum, VertexType vertexes[], EdgeInfo edges[]) {
    graph->vertexNum = vertexNum;
    graph->edgeNum = edageNum;
    
    // 寫入頂點數(shù)組 先將firstEdge置為NULL
    for (int i = 0; i < vertexNum; i++) {
        graph->adjList[i].data = vertexes[i];
        graph->adjList[i].firstEdge = NULL;
        graph->adjList[i].inDegree = 0;
    }
    
    EdgeNode *eNode;
    for (int i = 0; i < edageNum; i++) {
        // 先生成邊的結(jié)尾結(jié)點
        eNode = (EdgeNode *)malloc(sizeof(EdgeNode));
        eNode->adjvex = edges[i].endIndex;
        eNode->weight = edges[i].weight;
        // 頭插法
        eNode->next = graph->adjList[edges[i].startIndex].firstEdge;
        graph->adjList[edges[i].startIndex].firstEdge = eNode;
        graph->adjList[edges[i].endIndex].inDegree += 1;
    }
}

void printAdjListGraph(AdjListGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("\n");
        EdgeNode *eNode = graph.adjList[i].firstEdge;
        printf("頂點: %d 入度: %d 邊表:", graph.adjList[i].data, graph.adjList[i].inDegree);
        while (eNode) {
            printf("%d->%d(w:%d) ", graph.adjList[i].data, eNode->adjvex, eNode->weight);
            eNode = eNode->next;
        }
    }
    printf("\n");
}

按照拓撲排序的方式對圖進行拓撲排序，我們在排序的過程中，即可生成頂點對應(yīng)的事件最早發(fā)生時間數(shù)組。

// 事件最早發(fā)生時間數(shù)組
int *etvs;
// 存儲拓撲序列
int *topoStack;
int top2;

TStatus topologicalOrder(AdjListGraph *graph) {
    etvs = (int *)malloc(sizeof(int) * graph->vertexNum);
    int *stack = (int *)malloc(sizeof(int) * graph->vertexNum);
    int top = -1;
    // 將入度為0的頂點入棧
    for (int i = 0; i < graph->vertexNum; i++) {
        if (graph->adjList[i].inDegree == 0) {
            top += 1;
            stack[top] = i;
        }
        etvs[i] = 0;
    }
    
        
    // 棧頂元素
    int stackTop;
    // 記錄輸出的頂點個數(shù)
    int count;
    
    // 存儲拓撲排序
    topoStack = (int *)malloc(sizeof(int) * graph->vertexNum);
    top2 = -1;
    
    EdgeNode *eNode;
    while (top != -1) {
        stackTop = stack[top];
        top -= 1;
        top2 += 1;
        topoStack[top2] = stackTop;

        count += 1;
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            if (!(--graph->adjList[eNode->adjvex].inDegree)) {
                stack[++top] = eNode->adjvex;
            }
            // 得出每一個頂點 事件的最早發(fā)生時間
            // 頂點不同路徑之間比較 得到最大值 從上一個頂點到當前頂點有不同的路徑 找出最大值
            if (etvs[stackTop] + eNode->weight > etvs[eNode->adjvex]) {
                etvs[eNode->adjvex] = etvs[stackTop] + eNode->weight;
            }
            eNode = eNode->next;
        }
    }
    
    if (count < graph->vertexNum) {
        return T_ERROR;
    }
    
    return T_OK;
}

根據(jù)拓撲排序和事件最早發(fā)生時間，計算出事件最晚發(fā)生時間。然后對比頂點的最早發(fā)生時間和最晚發(fā)生時間是否相等，相等即為關(guān)鍵路徑。

// 事件最晚發(fā)生時間數(shù)組
int *ltvs;

void getKeyPath(AdjListGraph *graph) {
    ltvs = (int *)malloc(sizeof(int) * graph->vertexNum);
    
    // 默認把事件最晚發(fā)生時間都設(shè)置為最大的開始時間
    for (int i = 0; i < graph->vertexNum; i++) {
        ltvs[i] = etvs[graph->vertexNum-1];
    }
    
    // 計算事件最遲發(fā)生時間數(shù)組
    int stackTop;
    EdgeNode *eNode;
    while (top2 != -1) {
        stackTop = topoStack[top2];
        top2 -= 1;
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            // 最晚開始時間 = 下一個結(jié)點的開始時間 - 路徑權(quán)值
            if (ltvs[eNode->adjvex] - eNode->weight < ltvs[stackTop]) {
                ltvs[stackTop] = ltvs[eNode->adjvex] - eNode->weight;
            }
            eNode = eNode->next;
        }
    }
 
    
    int ete, lte;
    for (int i = 0; i < graph->vertexNum; i++) {
        eNode = graph->adjList[i].firstEdge;
        while (eNode) {
            ete = etvs[i];
            lte = ltvs[eNode->adjvex] - eNode->weight;
            // 最早開始時間等于最晚開始時間 則該路徑就為關(guān)鍵路徑
            if (ete == lte) {
                printf("<V%d-V%d> length:%d\n", graph->adjList[i].data, graph->adjList[eNode->adjvex].data, eNode->weight);
            }
            eNode = eNode->next;
        }
    }
}

void keyPathTest() {
    int vertexNumber = 10;
    int edgeNumber   = 13;
    int starts[]     = {0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8};
    int ends[]       = {1, 2, 4, 3, 3, 5, 4, 6, 7, 7, 9, 8, 9};
    int weights[]    = {3, 4, 6, 5, 8, 7, 3, 9, 4, 6, 2, 5, 3};

    EdgeInfo *eInfos = malloc(sizeof(EdgeInfo) * edgeNumber);
    initEdgeInfos(edgeNumber, starts, ends, weights, eInfos);
    
    AdjListGraph graph;
    VertexType vertexes[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    initAdjListGraph(&graph, vertexNumber, edgeNumber, vertexes, eInfos);
    
    TStatus st = topologicalOrder(&graph);
    printf("\n%s是AOV網(wǎng)\n", st == T_OK ? "": "不");
    getKeyPath(&graph);
}

// 控制臺輸出
是AOV網(wǎng)

<V0-V2> length:4
<V2-V3> length:8
<V3-V4> length:3
<V4-V7> length:4
<V7-V8> length:5
<V8-V9> length:3

$m$ 個頂點， $n$ 條弧的AOV網(wǎng)，拓撲排序的時間復(fù)雜度為 $O(m+n)$ ，而后進行處理的時間復(fù)雜度為 $O(m) + O(m+n) + O(m+n)$ ，所以求關(guān)鍵路徑的整體時間復(fù)雜度為 $O(m+n)$ 。