针对带解决的某问题,其优先级限制下的并行任务的排序就是该问题的关键路径
该问题可以转化为无环加权有向图求最长路径
测试代码
//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;
}
暂无评论
注册用户登录后才能发表或者回复评论,请先登录 或 注册。