关键路径算法c++实现
时间: 2023-09-14 10:06:33 浏览: 65
关键路径算法(Critical Path Method,CPM)是一种用于确定项目关键路径的方法,它是一种基于网络图的算法。下面是一个基于邻接表的 C++ 实现:
```C++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
// 邻接表存储图
struct edge {
int to, weight;
edge(int to, int weight) : to(to), weight(weight) {}
};
const int MAXN = 1005;
vector<edge> G[MAXN]; // 存储图
int inDegree[MAXN]; // 存储节点的入度
int earliest[MAXN]; // 存储节点的最早开始时间
int latest[MAXN]; // 存储节点的最晚开始时间
int path[MAXN]; // 存储关键路径
bool vis[MAXN]; // 标记节点是否被访问
// 拓扑排序,求每个节点的最早开始时间
void topoSort(int n) {
queue<int> q;
memset(earliest, 0, sizeof(earliest));
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
earliest[i] = 0;
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].to;
int w = G[u][i].weight;
inDegree[v]--;
earliest[v] = max(earliest[v], earliest[u] + w);
if (inDegree[v] == 0) {
q.push(v);
}
}
}
}
// 求每个节点的最晚开始时间
void latestTime(int n) {
memset(latest, 0x3f, sizeof(latest));
latest[n] = earliest[n];
for (int i = n - 1; i >= 1; i--) {
for (int j = 0; j < G[i].size(); j++) {
int v = G[i][j].to;
int w = G[i][j].weight;
latest[i] = min(latest[i], latest[v] - w);
}
}
}
// 求关键路径
void searchPath(int u) {
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].to;
int w = G[u][i].weight;
if (earliest[u] + w == earliest[v] && latest[u] - w == latest[v]) {
path[v] = 1;
if (!vis[v]) {
searchPath(v);
}
}
}
}
// 主函数
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back(edge(v, w));
inDegree[v]++;
}
topoSort(n);
latestTime(n);
searchPath(1);
cout << "关键路径为:";
for (int i = 1; i <= n; i++) {
if (path[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
输入格式为:
```
节点个数 边数
起点 终点 权值
起点 终点 权值
...
```
输出关键路径。