c/c++求解圖的關鍵路徑 critical path 上圖表示一個工程，工程以V1為起始子工程，V9為終止子工程。 由圖可以看出，要開工V5工程，必須在完成工程V2和V3後才可以。 完成V2需要a1（6）個小時，完成V3需要a2(4)個小時。假設V2和V3同時開工，V3就會提前2個小時完工，但是這 ...
c/c++求解圖的關鍵路徑 critical path
上圖表示一個工程，工程以V1為起始子工程，V9為終止子工程。
由圖可以看出，要開工V5工程，必須在完成工程V2和V3後才可以。
完成V2需要a1（6）個小時，完成V3需要a2(4)個小時。假設V2和V3同時開工，V3就會提前2個小時完工，但是這時V2還沒有完工，所以V5還不能開始。所以為了要開工V5必須V2要完成，V3即使晚開工2個小時，也不會耽誤V5的開工，所以V2就是V5的 關鍵路徑（Critical Path）。
有2個問題：(1)完成整個工程至少需要多少時間。(2)哪些子工程是影響總工程進度的關鍵？
(1)的答案：關鍵路徑上的時間總和是完成整個工程至少需要的時間。
(2)的答案：關鍵路徑上的工程是影響總工程進度的關鍵。
查找關鍵路徑的目的：
辨別哪些是關鍵工程，以便爭取提高關鍵工程的效率，縮短整個工期。
從上圖可以得知，工程V6延遲3天開工，或者延遲3個完成都不會影響項目的工期，所以V6不在關鍵路徑上。
實現思路：
假設e(i)表示活動a(i)的最早開始時間，在不推遲整個工程完成的前提下，用l(i)表示活動a(i)的最遲開始時間。兩者之差表示完成活動a(i)的時間餘量。餘量為0的活動就是關鍵活動，所以連接此活動的2個頂點就是關鍵路徑上的頂點。可以看出，即使提前完成非關鍵活動，也不能加快工程的進度。
辨別關鍵活動就是要找到e(i) = l(i)的活動。為了求得活動的e(i)和l(i)，首先應求得事件（頂點）的最早發生時間ve(i)和最遲發生時間vl(i)。如果活動a(i)，由邊<j, k>表示，其持續時間記為dut(<j, k>),則有如下公式：
e(i) = ve(i)
l(i) = vl(k) - dut(<j, k>)
ve的求法用拓撲排序
vl的求法用逆拓撲排序
求下圖的關鍵路徑
critical_path.h
#ifndef __criticalpath__
#define __criticalpath__
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#define Default_vertex_size 10
#define T char//dai biao ding dian de lei xing
#define E int
#define MAX_COST 0x7FFFFFFF
typedef struct GraphMtx{
int MaxVertices;//zui da ding dian shu liang]
int NumVertices;//shi ji ding dian shu liang
int NumEdges;//bian de shu lian
T* VerticesList;//ding dian list
int** Edge;//bian de lian jie xin xi, bu shi 0 jiu shi 1
}GraphMtx;
//chu shi hua tu
void init_graph(GraphMtx* gm);
//列印二維數組
void show_graph(GraphMtx* gm);
//插入頂點
void insert_vertex(GraphMtx* gm, T v);
//添加頂點間的線
void insert_edge(GraphMtx* gm, T v1, T v2, E cost);
//取得與v頂點有連線的第一個頂點
int getNeighbor(GraphMtx* gm, T v);
//取得與v1頂點，v1頂點之後的v2頂點的之後的有連線的第一個頂點
int getNextNeighbor(GraphMtx* gm, T v1, T v2);
E getWeight(GraphMtx* g, int v1, int v2);
//求解關鍵路徑
void critical_path(GraphMtx* g);
#endif
critical_path.c
#include "critical_path.h"
void init_graph(GraphMtx* gm){
gm->MaxVertices = Default_vertex_size;
gm->NumEdges = gm->NumVertices = 0;
//kai pi ding dian de nei cun kong jian
gm->VerticesList = (T*)malloc(sizeof(T) * (gm->MaxVertices));
assert(NULL != gm->VerticesList);
//創建二維數組
//讓一個int的二級指針，指向一個有8個int一級指針的數組
//開闢一個能存放gm->MaxVertices個int一級指針的記憶體空間
gm->Edge = (int**)malloc(sizeof(int*) * (gm->MaxVertices));
assert(NULL != gm->Edge);
//開闢gm->MaxVertices組，能存放gm->MaxVertices個int的記憶體空間
for(int i = 0; i < gm->MaxVertices; ++i){
gm->Edge[i] = (int*)malloc(sizeof(int) * gm->MaxVertices);
}
//初始化二維數組
//讓每個頂點之間的邊的關係都為不相連的
for(int i = 0; i < gm->MaxVertices; ++i){
for(int j = 0; j < gm->MaxVertices; ++j){
gm->Edge[i][j] = 0;
}
}
}
//列印二維數組
void show_graph(GraphMtx* gm){
printf(" ");
for(int i = 0; i < gm->NumVertices; ++i){
printf("%c ", gm->VerticesList[i]);
}
printf("\n");
for(int i = 0; i < gm->NumVertices; ++i){
//在行首,列印出頂點的名字
printf("%c:", gm->VerticesList[i]);
for(int j = 0; j < gm->NumVertices; ++j){
printf("%d ", gm->Edge[i][j]);
}
printf("\n");
}
printf("\n");
}
//插入頂點
void insert_vertex(GraphMtx* gm, T v){
//頂點空間已滿，不能再插入頂點了
if(gm->NumVertices >= gm->MaxVertices){
return;
}
gm->VerticesList[gm->NumVertices++] = v;
}
int getVertexIndex(GraphMtx* gm, T v){
for(int i = 0; i < gm->NumVertices; ++i){
if(gm->VerticesList[i] == v)return i;
}
return -1;
}
//添加頂點間的線
void insert_edge(GraphMtx* gm, T v1, T v2, E cost){
if(v1 == v2)return;
//查找2個頂點的下標
int j = getVertexIndex(gm, v1);
int k = getVertexIndex(gm, v2);
//說明找到頂點了,並且點之間還沒有線
if(j != -1 && k != -1 && gm->Edge[j][k] != 1){
//因為是有方向，所以更新1個值
gm->Edge[j][k] = cost;
//邊數加一
gm->NumEdges++;
}
}
//取得與某頂點有連線的第一個頂點
int getNeighbor(GraphMtx* gm, T v){
int p = getVertexIndex(gm, v);
if(-1 == p)return -1;
for(int i = 0; i < gm->NumVertices; ++i){
if(gm->Edge[p][i] != 0)
return i;
}
return -1;
}
//取得與v1頂點，v1頂點之後的v2頂點的之後的有連線的第一個頂點
int getNextNeighbor(GraphMtx* gm, T v1, T v2){
if(v1 == v2)return -1;
int p1 = getVertexIndex(gm, v1);
int p2 = getVertexIndex(gm, v2);
if(p1 == -1 || p2 == -1)return -1;
for(int i = p2 + 1; i < gm->NumVertices; ++i){
if(gm->Edge[p1][i] != 0)
return i;
}
return -1;
}
E getWeight(GraphMtx* g, int v1, int v2){
if(v1 == -1 || v2 == -1)return 0;
return g->Edge[v1][v2];
}
//求解關鍵路徑
void critical_path(GraphMtx* g){
int n = g->NumVertices;
//最早開始時間數組
int* ve = (int*)malloc(sizeof(int) * n);
//最晚開始時間數組
int* vl = (int*)malloc(sizeof(int) * n);
assert(NULL != ve && NULL != vl);
for(int i = 0; i < n; ++i){
ve[i] = 0;
vl[i] = MAX_COST;
}
int j, w;
//ve
for(int i = 0; i < n; ++i){
j = getNeighbor(g, g->VerticesList[i]);
while(j != -1){
w = getWeight(g, i, j);
if(ve[i] + w > ve[j]){
ve[j] = ve[i] + w;
}
j = getNextNeighbor(g,g->VerticesList[i],g->VerticesList[j]);
}
}
//ve 的結果看下圖a
//vl
vl[n-1] = ve[n-1];
for(int i = n - 2; i > 0; --i){
j = getNeighbor(g, g->VerticesList[i]);
while(j != -1){
w = getWeight(g, i, j);
if(vl[j] - w < vl[i]){
vl[i] = vl[j] - w;
}
j = getNextNeighbor(g,g->VerticesList[i],g->VerticesList[j]);
}
}
//vl 的結果看下圖b
int e, l;
for(int i = 0; i < n; ++i){
j = getNeighbor(g, g->VerticesList[i]);
while(j != -1){
e = ve[i];
l = vl[j] - getWeight(g, i, j);
if(e == l){
printf("<%c, %c>是關鍵路徑\n",g->VerticesList[i],g->VerticesL\
ist[j]);
}
j = getNextNeighbor(g,g->VerticesList[i],g->VerticesList[j]);
}
}
free(ve);
free(vl);
}
圖a
圖b
critical_path_main.c
#include "critical_path.h"
int main(){
GraphMtx gm;
//初始化圖
init_graph(&gm);
//插入頂點
insert_vertex(&gm, 'A');
insert_vertex(&gm, 'B');
insert_vertex(&gm, 'C');
insert_vertex(&gm, 'D');
insert_vertex(&gm, 'E');
insert_vertex(&gm, 'F');
insert_vertex(&gm, 'G');
insert_vertex(&gm, 'H');
insert_vertex(&gm, 'I');
//添加連線
insert_edge(&gm, 'A', 'B', 6);
insert_edge(&gm, 'A', 'C', 4);
insert_edge(&gm, 'A', 'D', 5);
insert_edge(&gm, 'B', 'E', 1);
insert_edge(&gm, 'C', 'E', 1);
insert_edge(&gm, 'D', 'F', 2);
insert_edge(&gm, 'E', 'G', 9);
insert_edge(&gm, 'E', 'H', 7);
insert_edge(&gm, 'F', 'H', 4);
insert_edge(&gm, 'G', 'I', 2);
insert_edge(&gm, 'H', 'I', 4);
//列印圖
show_graph(&gm);
//求解關鍵路徑
critical_path(&gm);
}
編譯方法：gcc -g critical_path.c critical_path_main.c
