图的应用:优先级限制下的并行任务调度(CMP关键路径) -- C++实现


针对带解决的某问题,其优先级限制下的并行任务的排序就是该问题的关键路径

该问题可以转化为无环加权有向图求最长路径

测试代码

//main.cpp

#include <time.h>
#include<windows.h>


#include "Component.h"
#include "EdgesWeightDirectionGraph.h"


using namespace jay;


int main(int argc, char* argv[])
{
	// 
	EdgesWeightDirectionGraph<double,int> gra;
	
	int iCount;// 顶点的个数(任务编号由 0 至 iCount-1 共iCount个)

	cin>>iCount;

	int iBegin = 2 * iCount ;    // 起点(额外添加)
	int iEnd   = 2 * iCount + 1; // 终点(额外添加)

	for (int i=0;i<iCount;i++)
	{
		int iCurentTask; // 当前顶点(任务编号/任务的起始顶点)
		cin>>iCurentTask;

		double weight;
		cin>>weight; // 权重

		// 任务的边
		gra.AddEdge(iBegin,iCurentTask,0.0); // 起点到当前任务的起始顶点
		gra.AddEdge(iCurentTask,iCurentTask + iCount,weight); // 当前任务的起始顶点到当前任务的结束顶点
		gra.AddEdge(iCurentTask + iCount,iEnd,0.0); // 当前任务的结束顶点到终点

		// 优先级的边
		int iAfterCount;// 需当前任务完成才能开始的任务个数
		cin>>iAfterCount;
		for (int j=0;j<iAfterCount;j++)
		{
			int iAferTask;
			cin>>iAferTask;

			gra.AddEdge(iCurentTask + iCount,iAferTask,0.0); // 当前任务的结束顶点到后续任务的起始顶点

		}

	}
	
	gra.Show();
	if (gra.hasLoop())
	{
		cout << "图存在环,无法进行拓扑排序"<<endl;
		return 0;
	}

	gra.TopologicalSort();

 	gra.AcyclicLongnestPath(iBegin);
 
  	gra.pathTo(1);

	gra.pathTo(5);

	gra.pathTo(8); 
	gra.pathTo(2);
	cout << "全部任务输出:" <<endl;
	cout.flags(ios::right);
	cout <<  setw(10)<< "任务编号"  <<  setw(10)<< "开始时间"  <<  setw(10)<< "结束时间" << endl;
	for (int i=0;i<iCount;i++)
	{
		cout <<  setw(10)<< i  <<  setw(10)<< gra.distTo(i)  <<  setw(10)<< gra.distTo(i+iCount) << endl;
	}

	 cout << "总用时:" <<gra.distTo(iEnd) <<endl;


}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。