|
前言
Live beautifully, dream passionately, love completely.
Name：Willam
Time：2017/3/7 1、AOE-网介绍我们在学习拓扑排序（如果没学，可以看看这篇博客：拓扑排序详解）的时候，已经接触了什么是AOV-网，AOV-网是优先考虑顶点的思路，而我们也同样可以优先考虑边，这个就是AOE-网的思路。 若在带权的有向无环图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向无环图称为AOE网。记住AOE-网只是比AOV-网多了一个边的权重，而且AOV-网一般是设计一个庞大的工程各个子工程实施的先后顺序，而我们的AOE-网就是不仅仅关系整个工程中各个子工程的实施的先后顺序，同时也关系整个工程完成最短时间。 因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。 AOE-网还有一个特点就是：只有一个起点（入度为0的顶点）和一个终点（出度为0的顶点），并且AOE-网有两个待研究的问题： 完成整个工程需要的时间 哪些活动是影响工程进度的关键
2、名词解释
假设起点是vo，则我们称从v0到vi的最长路径的长度为vi的最早发生时间，同时，vi的最早发生时间也是所有以vi为尾的弧所表示的活动的最早开始时间，使用e（i）表示活动ai最早发生时间，除此之外，我们还定义了一个活动最迟发生时间，使用l（i）表示，不推迟工期的最晚开工时间。我们把e（i）=l（i）的活动ai称为关键活动，因此，这个条件就是我们求一个AOE-网的关键路径的关键所在了。 所以，我们现在要求的就是每弧所对应的e（i）和l（i），求这两个变量的公式是： e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)
变量的介绍： 首先我们假设活动a（i）是弧<j,k>上的活动，j为弧尾顶点，k为弧头（有箭头的一边），ve（j）代表的是弧尾j的最早发生时间，vl（k）代表的是弧头k的最迟发生时间dut（<j,k>）代表该活动要持续的时间，既是弧的权值
好了，先在我们知道了求e（i）和l（i）就必须先知道各个顶点的ve和vl了，所以下面我们就来求每个顶点ve和vl。其中，我们要知道ve和vl是要分开来求的。 先求ve，从ve（0）=0开始往前推（其实就是从起点开始往后，求各个顶点最早发生时间），公式如下： ve（j）=Max{ve{i}+dut（<i,j>）};<i,j>属于T，j=1,2.....n-1，其中T是所有以第j个顶点为头的弧的集合。n为顶点的个数
下面我们继续求：各个顶点的vl，vl是从vl（n-1）=ve（n-1）往后推进（其实就是从终点开始往前求各个顶点的最迟发生时间，其中终点的ve和vl是相等的） vl（i）=Min{vl(j)-dut(<i,j>)}<i,j>属于S，i=n-2,n-3.....0其中，S是所有以第i个顶点为尾的弧的集合
3、求关键路径的步骤输入顶点数和边数，已经各个弧的信息建立图 从源点v1出发，令ve[0]=0;按照拓扑序列往前求各个顶点的ve。如果得到的拓扑序列个数小于网的顶点数n，说明我们建立的图有环，无关键路径，直接结束程序 从终点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑序列，往后求其他顶点vl值 根据各个顶点的ve和vl求每个弧的e（i）和l（i），如果满足e（i）=l（i），说明是关键活动。
4、求关键路径的代码实现/************************************************************//* 程序作者：Willam *//* 程序完成时间：2017/3/6 *//* 有任何问题请联系：2930526477@qq.com *//************************************************************///@尽量写出完美的程序#pragma once//#pragma once是一个比较常用的C/C++杂注，//只要在头文件的最开始加入这条杂注，//就能够保证头文件只被编译一次。/*求解关键路径问题，必须是有向无环图才有关键路径*/#include<iostream>#include<stack>#include<string>using namespace std;//表结点struct ArcNode { int start; //弧尾的顶点的下标 int end; //弧头的顶点的下标 ，有箭头的一方 int weight; //弧的权重 ArcNode * next; //下一条弧};//头结点struct Vnode { ArcNode * firstarc; //第一条依附在该该顶点的弧 string data;};class Graph_DG {private: int vexnum; //顶点个数 int edge; //边的条数 Vnode * arc; //邻接表 int *indegree; //各个顶点的入度情况 stack<int> List; //拓扑序列中各个边的情况 int * ve; //记录每个顶点的最早发生时间 int * vl; //记录每个顶点最迟发生时间public: Graph_DG(int vexnum, int edge); ~Graph_DG();//析构函数 bool check_edge_value(int, int, int); //检查边的信息是否合法 void createGraph();//创建一个新的图 void print();//打印图的邻接表 bool topological_sort(); bool CriticalPath();};
#include'CriticalPath.h'Graph_DG::Graph_DG(int vexnum, int edge) { /* 初始化一些基本的信息， 包括边和顶点个数，各个顶点入度数组，邻接表的等 */ this->vexnum = vexnum; this->edge = edge; this->arc = new Vnode[this->vexnum]; this->indegree = new int[this->vexnum]; this->ve = new int[this->vexnum]; this->vl = new int[this->vexnum]; for (int i = 0; i < this->vexnum; i++) { this->indegree[i] = 0; this->ve[i] = 0; this->arc[i].firstarc = NULL; this->arc[i].data = 'v' + to_string(i + 1); }}//释放内存空间Graph_DG::~Graph_DG() { ArcNode * p, *q; for (int i = 0; i < this->vexnum; i++) { if (this->arc[i].firstarc) { p = this->arc[i].firstarc; while (p) { q = p->next; delete p; p = q; } } } delete[] this->arc; delete[] this->indegree;}//判断我们每次输入的的边的信息是否合法//顶点从1开始编号bool Graph_DG::check_edge_value(int start, int end,int weight) { if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) { return false; } return true;}void Graph_DG::createGraph() { cout << '请输入每条边的起点和终点的编号（顶点从1开始编号）以及每条边的权重' << endl; int count = 0; //记录初始化边的条数 int start, end, weight; while (count != this->edge) { cin >> start >> end >> weight; while (!check_edge_value(start, end, weight)) { cout << '输入的信息不合法，请重新输入：' << endl; cin >> start >> end >> weight; } ArcNode * temp = new ArcNode; temp->start = start-1; temp->end = end-1; temp->weight = weight; temp->next = NULL; //如果当前顶点的还没有边依附时， ++indegree[temp->end]; //对应的弧头的顶点的入度加1 if (this->arc[start - 1].firstarc == NULL) { this->arc[start - 1].firstarc = temp; } else { ArcNode * now = this->arc[start - 1].firstarc; while (now->next) { now = now->next; }//找到该链表的最后一个结点 now->next = temp; } ++count; }}void Graph_DG::print() { cout << '图的邻接表为：' << endl; int count = 0; while (count != this->vexnum) { cout << this->arc[count].data << ' '; ArcNode * temp = this->arc[count].firstarc; while (temp) { cout << '<' << this->arc[temp->start].data << ',' << this->arc[temp->end].data << '>=' << temp->weight << ' '; temp = temp->next; } cout << '^' << endl; ++count; }}bool Graph_DG::topological_sort() { cout << '图的拓扑序列为：' << endl; stack<int> s; //保存入度为0的顶点下标 ArcNode * temp; int i; for (i = 0; i < this->vexnum; i++) { if (!indegree[i]) s.push(i); //入度为0 ，则入栈 } //count用于计算输出的顶点个数 int count = 0; while (!s.empty()) {//如果栈为空，退出循环 i = s.top(); //i等于栈顶的元素 s.pop(); cout << this->arc[i].data << ' ';//输出拓扑序列 temp = this->arc[i].firstarc; this->List.push(i); while (temp) { if (!(--indegree[temp->end])) {//如果入度减少到为0，则入栈 s.push(temp->end); } //同时更新ve的值 if ((ve[i] + temp->weight) > ve[temp->end]) { ve[temp->end] = ve[i] + temp->weight; } temp = temp->next; } ++count; } if (count == this->vexnum) { cout << endl; return true; } cout << '此图有环，无拓扑序列' << endl; return false;//说明这个图有环}bool Graph_DG::CriticalPath() { if (!this->topological_sort()) { cout << '此图有环，无关键路径' << endl; return false; } cout << '图的关键路径为：' << endl; //初始化vl的值都为ve[this->vexnum-1] int k; for (k = 0; k < this->vexnum; k++) { vl[k] = ve[this->vexnum - 1]; } ArcNode * temp; while (!this->List.empty()) { k = List.top();//从逆拓扑排序开始，求vl List.pop(); temp = this->arc[k].firstarc; while (temp) { //dut<k,temp->end>，从以第k个顶点为弧尾集合中选择一个最小的值 //来作为第i个顶点的最迟发生时间 if (vl[k] > (vl[temp->end] - temp->weight)) { vl[k] = vl[temp->end] - temp->weight; } temp = temp->next; } } int ee; int el; for (k = 0; k < this->vexnum; k++) { temp= temp = this->arc[k].firstarc; while (temp) { ee = ve[k]; el = vl[temp->end] - temp->weight; if (ee == el) {//这两个值相等，说明它为关键活动： cout << this->arc[k].data << '----' << this->arc[temp->end].data << '=' << temp->weight << endl; } temp = temp->next; } }}
#include'CriticalPath.h'//检验输入边数和顶点数的值是否有效，可以自己推算为啥：//顶点数和边数的关系是：((Vexnum*(Vexnum - 1)) / 2) < edgebool check(int Vexnum, int edge) { if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge) return false; return true;}int main() { int vexnum; int edge; cout << '输入图的顶点个数和边的条数：' << endl; cin >> vexnum >> edge; while (!check(vexnum, edge)) { cout << '输入的数值不合法，请重新输入' << endl; cin >> vexnum >> edge; } Graph_DG graph(vexnum, edge); graph.createGraph(); graph.print(); graph.CriticalPath(); system('pause'); return 0;}
构造下图：
 输入： 9 111 2 61 3 41 4 52 5 13 5 14 6 25 7 95 8 76 8 47 9 28 9 4
输出：
 从输出可以看出，这个图有两条关键路径：
第一条就是： v1--v2--v5--v7--v9
第二条是： v1--v2--v5--v8--v9
我们在构造下图的关键路径：
 输入： 6 81 2 31 3 22 4 22 5 33 4 43 6 34 6 25 6 1
输出：
 从输出可以看出，这个图有一条关键路径： v1--v3--v4--v6
|
