CriticalPath(关键路径)

admin管理员组

文章数量:1530022

  用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。例如：

　　图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。

　　1)AOV 网具有的性质

• 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
• 只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。
• 表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。

　　2)由事件vj的最早发生时间和最晚发生时间的定义，可以采取如下步骤求得关键活动：

　　A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。

• Ve(k)=max{ve(j)+dut(<j,k>)} （ 1.1 ）
• j ∈ T

　　其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。

　　如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

　　B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:

• vl(j)=min{vl(k)-dut(<j,k>)}
• k ∈ S

　　其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。

　　C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j)；最晚开始时间：

• l(i)=vl(k)-dut(<j,k>)

　　若某条弧满足 e(i)=l(i) ，则它是关键活动。

CPM.H

//#pragma once
#ifndef CPM_H
#define CPM_H
#include<iostream>
#include<string>
using namespace std;


struct ArcNode
{
	int start;
	int end;
	int weight;
	ArcNode* next;
};
struct Vnode
{
	ArcNode* firstarc;
	string data;

};
struct  Graph
{
	int vex;
	int edg;
    Vnode * arc;//链接链表
	int * indegree;
	int *ve;//每个顶点的最早发生时间
	int *vl;//每个顶点的最迟发生时间
};

void CreateGraph(Graph& g);
void PrintGraph(Graph g);
void CriticalPath(Graph &g);
#endif

CPM.cpp 

#include"CPM.h"
#define max 1000000
void CreateGraph(Graph& g)
{
	cout << "请输入顶点数" << endl;
	cin >> g.vex;
	cout << "请输入边数" << endl;
	cin >> g.edg;
	g.arc = new Vnode[g.vex];
	g.indegree = new int[g.vex];
	g.ve = new int[g.vex];
	g.vl = new int[g.vex];
	for (int i = 0;i < g.vex;i++)
	{
		g.indegree[i] = 0;
		g.ve[i] = 0;
		g.arc[i].firstarc = NULL;
		g.arc[i].data = "v" + to_string(i);
	}
	cout << "请输入每条边的起点和终点（编号从0开始），以及权重" << endl;
	int count = 0;
	int start;
	int end;
	int weight;
	for(int i=0;i<g.edg;i++)
	{
		cin >> start >> end >>weight;
		ArcNode* temp=new ArcNode;
		temp->start = start;
		temp->end = end;
		temp->weight = weight;
		temp->next = NULL;
		++g.indegree[temp->end];
		if (g.arc[start].firstarc == NULL)
		{
			g.arc[start].firstarc = temp;
		}
		else
		{
			ArcNode* now = g.arc[start].firstarc;
			while (now->next)
			{
				now = now->next;
			}
			now->next = temp;
		}
		
	}


}

void PrintGraph(Graph g)
{
	cout << "图的链接链表为" << endl;
	for(int i=0;i<g.vex;i++)
	{
		cout << g.arc[i].data << " ";
		ArcNode* temp =g.arc[i].firstarc;
		while (temp)
		{
			cout<< "<" << g.arc[temp->start].data
				<< ","
				<< g.arc[temp->end].data
				<< ">="
				<< temp->weight
				<< " ";
			temp = temp->next;
		}
		cout <<  endl;
		
	}

}
void CriticalPath(Graph &g)
{/***********最早发生时间******/
	for (int i = 0;i < g.vex;i++)
	{
		ArcNode* temp = g.arc[i].firstarc;
		while (temp)
		{
			if (g.ve[i] + temp->weight > g.ve[temp->end])
				g.ve[temp->end] = g.ve[i] + temp->weight;
			temp = temp->next;

		}

    }
	/***********最晚发生时间************/
	for (int i = 0;i < g.vex;i++)
	{
		g.vl[i] = g.ve[g.vex - 1];
	}
	for (int i = g.vex - 2;i >= 0;i--)
	{
		ArcNode* temp = g.arc[i].firstarc;
		while (temp)
		{
			if (g.vl[temp->end] - temp->weight < g.vl[i])
				g.vl[i] = g.vl[temp->end] - temp->weight;
			temp = temp->next;

		}
	}
	int e;
	int l;
	for (int i = 0;i < g.vex;i++)
	{
		ArcNode*temp = g.arc[i].firstarc;
		while (temp)
		{
			e = g.ve[i];
			l = g.vl[temp->end] - temp->weight;
			if(e==l)
			{
				cout << g.arc[i].data
					<< "----"
					<< g.arc[temp->end].data
					<< "="
					<< temp->weight
					<< endl;
			}
			temp = temp->next;
		}

	}

}

main.cpp 

#include<iostream>
#include"CPM.h"
using namespace std;

int main()
{
	Graph g;
	CreateGraph(g);
	PrintGraph(g);
	CriticalPath(g);
}

本文标签： 路径关键CriticalPath