关键路径

缘起

如上图所示, V1表示工程的开始, V9表示工程的结束. 其中的边表示相应的活动，而边上的数值表示活动要进行的天数. 对于上图节点的解读以V5为例. V5 表示要开始V5之后的活动（即v7和v8）的话, 需要完成V2和V3. 那么我们感兴趣的是, 完工最短要几天? 而且那一条图上的路径对应这个工期? 换言之, 图中哪条路径拖慢了整个工期. 再或者说, 哪条路径是这个工期的短板? 这条路径我们把它称为关键路径. 显然, 根据目测,v1->v2->v5->v8->v9 是关键路径, 整个工期是18天.

分析

令 e[i]和l[i] 为边i的最早开始时间和最晚开始时间. e即early，l即last. 例如边 i=<4,6>, 则

e[i] = 5; l[i] = 6

即活动a6最早第五天开始（毕竟要等活动a3搞完）, 最晚第6天开始（如果再晚的话, 则到达V8就大于>12天，而关键路径 V1->V3->V5->V8 是4+1+7=12，就影响了工期了）.

不难知道, 关键路径上的边一定是满足 e[i]=l[i]的. 即最早开工和最晚开工时间要一致. 我们想把求e[i]和l[i]这种求边的转换为求顶点的. 令 ve[i] 是顶点i的最早发生时间, 而vl[i]是顶点i(即事件i)的最晚发生时间,

令 i=<j,k>

则

e[i] = ve[j]

l[i] = vl[k] - i的权重

于是, 我们可以将求边的值转换为求顶点的值. 为什么要做这种转换呢? 因为求顶点的值能够更好的使用到我们的搜索算法.

我们下面考虑 ve和vl怎么求. 需要使用dp

ve[i] = max{ve[j]+<j,i>的权重}, j的取值范围是有边<j,i>,原因是我下一个节点的最早到达时间也一定要等之前最晚的那个

vl[i] = min{vl[j]-<i,j>的权重}，j的取值范围是有边<i,j>,原因是不能再晚了, 否则，vl[j]就更晚了.

注意上面的dp公式. 尤其是第一个, 表明 ve数组后一个的计算有赖于有边到它的顶点的相应值. 也就是说，计算任何一个顶点的ve值, 有一些值是必须计算的, 这不就是拓扑序吗? 而反观 vl数组的计算, 它是逆拓扑序. 所以我们必须要在拓扑序的过程中记下整个拓扑序. 或者使用dfs. 注意,为什么 ve的计算不方便使用dfs? 因为ve是根据所有入的边来计算的. 而vl 是根据所有出的边来计算的. 所以显然前者不方便使用dfs而只能使用拓扑序, 后者才方便使用dfs或者使用拓扑序.

综上, 我们知道如何判定一条边是关键活动，就是

1
ve[j]==vl[k] - i的权重，其中 i是从j到k的边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <vector>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

#define LOCAL
using namespace std;

#define MAX_VERTEX_NUM 10

struct Graph
{
	struct Edge
	{
		int end, weight; // end是边的终点. weight是边的权重
		Edge(int end, int weight):end(end), weight(weight){}
	};

	vector<Edge> vertex[MAX_VERTEX_NUM]; // 顶点数组

	typedef vector<Edge>::iterator it; // 定义迭代器

	int vertexnum, cnt, ve[MAX_VERTEX_NUM], vl[MAX_VERTEX_NUM], indeg[MAX_VERTEX_NUM]; // 实际的顶点个数, 实际顶点数的副本

	stack<int> s,t; // 用于维护拓扑序的两个栈

	bool isvisited[MAX_VERTEX_NUM]; // 是否访问过

	char path[MAX_VERTEX_NUM]; // 用于保存关键路径

	int n; // 关键路径的条数

	Graph()
	{
		memset(indeg, 0, sizeof(indeg)); // 初始化入度域
		puts("请输入顶点的个数\n");
		scanf("%d", &vertexnum);
		cnt = vertexnum;
		puts("请输入各边的起点、终点和权重,起点在前, 终点在后, 不同边换行");
		int start, end, weight;
		while(~scanf("%d%d%d", &start, &end, &weight))
		{
			vertex[start].push_back(Edge(end, weight));
			indeg[end]++;
		}
	}

	bool keypath() // 关键路径算法
	{
		n = 0;
		memset(isvisited, 0, sizeof(isvisited));
		memset(ve,0,sizeof(ve)); // 因为ve是求最大
		memset(vl, 0x3f, sizeof(vl)); // 因为 vl 是求最小
		// 初始化栈s
		for (int i = 0; i< vertexnum;i++)
		{
			if (!indeg[i])
			{
				ve[i] = 0; // 拓扑序起点的最早开始时间是0
				s.push(i);
			}
		}
		while(!s.empty())
		{
			int top = s.top();
			s.pop();
			cnt--;
			t.push(top); // 不能抛弃top, 因为计算vl依赖逆拓扑序. 而t的出栈顺序就是逆拓扑序，当然，如果你使用的是dfs求vl的话, 可以不使用t进行存储.
			for (it x = vertex[top].begin(); x!=vertex[top].end(); x++)
			{
				if (!(--indeg[x->end])) s.push(x->end);
				ve[x->end] = max(ve[x->end], ve[top] + x->weight); // 不论是否堕入0入度. 都是要更新ve[x->end]的, 因为top拓扑序位于x的前面 所以可以这样更新的, 这是ve的算法决定的
			}
		} // 此while循环结束之后, ve计算完毕.
		if (cnt) return false; // 说明不是dag, 算法结束
		cout<<"最短工期是"<<ve[t.top()] << endl; // 最短工期就是拓扑序的终点的ve值
		vl[t.top()] = ve[t.top()]; // 拓扑序的末端的 ve和vl的值是一样的
		// 开始计算vl
		while(!t.empty()) // t弹栈的顺序是逆拓扑序
		{
			int top = t.top();
			t.pop();
			for (it x = vertex[top].begin(); x!=vertex[top].end(); x++) vl[top] = min(vl[top], vl[x->end] - x->weight); // 这是vl的算法, 注意, 不用担心, 计算vl[top]的时候, 它需要的vl[x->end] 都存在 因为这是拓扑序决定的.
		} // 此while循环结束后, vl计算完毕
		// 上面的while和下面的for 二择一, 本质上就是 使用拓扑序或者 dfs 求 vl
		/*for (int i = 0; i< vertexnum; i++)
		{
			if (!isvisited[i])
			{
				isvisited[i] = true;
				dfs(i);
			}
		}*/
		// 扫描所有边， 根据 ve和vl 比较判定哪些是关键活动，这种办法不好, 因为会打印出
		/*
		<0, 1>
		<1, 4>
		<4, 6>
		<4, 7>
		<6, 8>
		<7, 8>
		因为有多重选择  所以下面的 for 算法不好
		*/
		/*for (int i = 0;i<vertexnum;i++)
		{
			for (it x = vertex[i].begin(); x!=vertex[i].end(); x++)
			{
				if (ve[i] == vl[x->end]-x->weight)
				{
					printf("<%d, %d>\n", i, x->end);
				}
			}
		}*/
		// 推荐使用下面的输出关键路径的算法
		memset(isvisited, 0, sizeof(isvisited));
		isvisited[0] = true;
		path[0] = '0';
		dfs_key(0,1);
		cout << "一共" << n << "条关键路径" <<endl;
	}

private:
	void dfs(int i) // i是当前节点
	{
		for (it x = vertex[i].begin(); x!=vertex[i].end();x++)
		{
			if (!isvisited[x->end])
			{
				isvisited[x->end] = true;
				dfs(x->end);
			}
			vl[i] = min(vl[i], vl[x->end] - x->weight); // 按照vl的算法
		}
	}

	void dfs_key(int i, int top) // i是当前节点, path[0,...top-1] 是进入此函数时的已经有的路径
	{
		if (i == 8) // 这里仅仅对测试数据写了该算法, 细致一点, 应该不难一般化, 譬如这里的8 其实就是拓扑序的终点
		{
			n++;
			path[top] = 0;
			puts(path);
			return;
		}
		for (it x = vertex[i].begin(); x!=vertex[i].end(); x++)
		{
			if (!isvisited[x->end] && vl[x->end] == ve[i]+x->weight)
			{
				isvisited[x->end] = true;
				path[top] = '0'+x->end; 
				dfs_key(x->end, top+1); // 注意, 这里必须要用top+1 而不是 top++ 因为for循环到下一次还要用top本身 而不是 top+1
				isvisited[x->end] = false; // 改回来, 因为是搜索
			}
		}
	}

};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	Graph g;
	cout << (g.keypath()? "无环":"不是dag") << endl;
#endif
	return 0;
}

测试数据

9
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 7 4
7 8 4
4 6 9
6 8 2
4 7 7