【图论】关键路径求法c++

int main() {

	int n = 6;

	float** mat = new float*[] {
			new float[] {0,	2,		3,		INF,	INF,	INF	},
			new float[] {INF,	0,		INF,	5,		INF,	INF	},
			new float[] {INF,	3,		0,		9,		4,		INF	},
			new float[] {INF,	INF,	INF,	0,		6,		2	},
			new float[] {INF,	INF,	INF,	INF,	0,		3	},
			new float[] {INF,	INF,	INF,	INF,	INF,	0	}
	};

	char** value = new char*[n]{
		"v1", "v2", "v3", "v4", "v5", "v6"
	};

	float *ve, *vl, *e, *l;
	int* criticalPath;
	int length;

	int** edges;
	int* topo;

	topologicalSort(mat, topo, n);
	int edgeNum = getEdges(mat, edges, n);
	aoe(mat, n, criticalPath, length, ve, vl, e, l);

	cout << "拓扑排序为：";
	for (int i = 0; i < n; ++i) {
		cout << value[topo[i]] << " ";
	}
	cout << "nn";

	cout << "共有" << edgeNum << "条边：n";
	for (int i = 0; i < edgeNum; ++i) {
		cout << value[edges[i][0]] << "-&gt;" << value[edges[i][1]] << ": " << mat[edges[i][0]][edges[i][1]] << endl;
	}
	cout << endl;

	for (int i = 0; i < n; ++i) {
		cout << 't' << value[i];
	}
	cout << endl;

	cout << "ve:";
	for (int i = 0; i < n; ++i) {
		cout << 't' << ve[i];
	}
	cout << endl;

	cout << "vl:";
	for (int i = 0; i < n; ++i) {
		cout << 't' << vl[i];
	}
	cout << "nn";

	for (int i = 0; i < edgeNum; ++i) {
		cout << 't' << value[edges[i][0]] << "->" << value[edges[i][1]];
	}
	cout << endl;

	cout << "e:";
	for (int i = 0; i < edgeNum; ++i) {
		cout << 't' << e[i];
	}
	cout << endl;

	cout << "l:";
	for (int i = 0; i < edgeNum; ++i) {
		cout << 't' << l[i];
	}
	cout << endl;

	cout << "l-e:";
	for (int i = 0; i < edgeNum; ++i) {
		cout << 't' << l[i] - e[i];
	}
	cout << "nn";

	cout << "关键路径为：";
	for (int i = 0; i < length; ++i) {
		cout << value[criticalPath[i]] << " ";
	}

	return 0;

}

运行结果如下：

代码007普通

打赏 收藏 海报 链接