admin管理员组文章数量:1567739
用顶点表示事件,弧表示活动,弧上的权值表示活动持续的时间的有向图叫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
版权声明:本文标题:CriticalPath(关键路径) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1726270153a1063725.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论