网站商务通弹出窗口图片更换设置,建设工程施工合同示范文本2021,内网网站建设流程,免费网络直播软件目录
文章目录
前言
一.最短路径
1.基本概念
1.1什么是源点#xff1f;
1.2什么是最短路径
2.作用 3.迪杰斯特拉算法
4. 弗洛伊德算法 4.1过程演示
二.拓扑排序
1.基本概念
1.1什么是有向无环图
1.2什么是活动
1.3什么是AOV网
1.4什么是拓扑序列
1.5什么是拓扑…目录
文章目录
前言
一.最短路径
1.基本概念
1.1什么是源点
1.2什么是最短路径
2.作用 3.迪杰斯特拉算法
4. 弗洛伊德算法 4.1过程演示
二.拓扑排序
1.基本概念
1.1什么是有向无环图
1.2什么是活动
1.3什么是AOV网
1.4什么是拓扑序列
1.5什么是拓扑排序
2.算法思想
2.1有向无环图
2.2有向有环图
3.思想的实现
三.关键路径
1.基本概念
1.1AOE网
1.2AOE网的源点和汇点
1.3什么是关键路径
1.4ETV
1.5LTV
1.6ETE
1.7LTE
2.关键路径算法
总结 文章目录 前言一、最短路径 1.基本概念2.作用3.迪杰斯特拉算法4.弗洛伊德算法二、拓扑排序 1.基本概念2.算法思想3.思想的实现三、关键路径 1.基本概念2.关键路径算法总结 前言
好久没更新了过完年啦现在更新一下叭 一.最短路径
1.基本概念
1.1什么是源点
路径起始的第一个顶点称为源点最后一个顶点称为终点。图下图中我们用红色标注出的就可以认为是一个路径V0 -V1 -V4 -V6 -V8的源点和终点但不要有误区其实图中的任何一个顶点都可作为源点或者终点源点与终点只是相对一条路径而言的 1.2什么是最短路径
对于无向图而言从源点V0到终点V8的最短路径就是从源点V0到终点V8所包含的边最少的路径.我们只需要从源点V0出发对图做广度优先搜索一旦遇到终点V8就终止。我们可以具体来看看如何得到无向图中源点V0到终点V8的最短路径。 第一步遍历顶点V0 第二步遍历顶点V0的邻接顶点V1和V2具体操作中我们使用队列来进行实现 第三步遍历顶点V1的邻接顶点V3和V4遍历顶点V2的邻接顶点V5 第四步遍历顶点V3的邻接顶点V6和V4的邻接顶点V7 第五步遍历顶点V6的邻接顶点V8发现正好是终点 由此可以得到图中从源点V0到终点V8的第一条一条最短路径 V0 -V1 -V3 -V6 -V8 。
2.作用
简单来说我们要从大兴机场到北京天安门如何规划路线才能换乘最少并且耗时最少呢这时候最短路径算法就派上用场了你每天使用的导航系统进行道路规划也同样依赖于底层的算法虽然现实情况可能更复杂一些但是学习最基础的算法对于我们日后的提升总有莫大的帮助。 3.迪杰斯特拉算法
迪杰斯特拉算法是一个单源点的一个最短路径算法也就是说我们这个算法会求得从一个顶点到其所有顶点的最短路径。 首先引入一个辅助变量D它的每一个分量D[i]表示当前所找到的从源点v到每一个顶点Vi的最短路径的长度它的初始状态为若从V到Vi有弧则D[i]为弧上的权值。否则D[i]为无穷大。显然,长度就为的路径就是从 v 出发的长度最短的一条最短路径。此路径为VVj 。我们直接看例子以下图为例 第一步初始化辅助向量D路径向量P 和 当前已求得顶点V0到Vj的最短路径的向量Final。 辅助向量D的初态为若从V0到Vj有弧则D[j]为弧上的权值否则D[j]为无穷大。对应到图中V0到V1有弧则D[1] 1 V0 到V2有弧则D[2] 5 到其他顶点没有弧则相应的用无穷表示。路径向量P用于存储最短路径下标的数组初始时全部置为零向量Final中值为1表示顶点V0到Vj的最短路径已求得V0到V0的最短路径当然是已求得所以将Final[V0]设置为1。接下来就是迪杰斯特拉算法的核心了。 第二步遍历源点V0, 找到源点V0的邻接顶点中距离最短的顶点即V1 V0到V1的最短路径为1已经求出更新Final[1] 1 第三步遍历顶点 V1找到顶点V1的邻接顶点V0 、V2 、V3 、V4 其中V0已经遍历过了不需要考虑。从V1到V2的距离是 3所以V0到V2的距离是 134小于辅助向量D中的距离 5则更新 D[2] 4从V1到V3的距离是 7所以V0到 V3 的距离是 178小于辅助向量中的D[3]则更新D[3] 8 从V1到V4的距离是 5所以V0到V4的距离是 156小于辅助向量中的D[4] 则更新D[4] 6相应的将顶点V2 、V3 、V4 的前驱结点更新为V1的下标 1。 接下来就是重复第二步、第三步 第四步遍历源点 V0, 找到从源点V0出发距离最短的且final0的顶点发现为 V2, 更新Final[2] 1 第五步遍历顶点V2并更新辅助向量 D 和 路径向量 P 。 第六步找到从源点V0出发距离最短的且final0的顶点发现为V4 , 更新final[4] 1 第七步遍历顶点V4并更新辅助向量D和路径向量P 第八步找到从源点V0出发距离最短的且final0的顶点发现为 V3 , 更新 Final[3] 1. 第九步遍历顶点V3并更新辅助向量 D 和 路径向量 P 第十步找到从源点V0出发距离最短的且final0的顶点发现为V5 , 更新final[5] 1 第十一步遍历顶点 V5 并更新辅助向量 D 和 路径向量 P 第十二步找到从源点 V0出发距离最短的且final0的顶点发现为 V6 , 更新 final[6] 1 第十三步遍历顶点V6并更新辅助向量 D 和 路径向量 P 第十四步找到从源点 V0出发距离最短的且final0的顶点发现为 V7 , 更新 final[7] 1 第十五步遍历顶点 V7 并更新辅助向量 D 和 路径向量 P 第十六步找到从源点 V0出发距离最短的且final0的顶点发现为 V8 , 更新 final[8] 1 .此时全部结点完毕算法结束 根据路径向量我们则可以得到从源点V0到终点V8的最短路径 #includestdio.h
#includestdlib.h
#define INF 65535
//基于带权无向图 ----O(|v|^2)
int g[105][105],flag[105],dist[105],path[105],nv,ne,s,end;
void dujkstra(){int minn,k;//最小的dist值 最小的dist值的点的下标 //初始化dist pathfor(int i0;inv;i){dist[i]INF;path[i]-1;}//确定起点自己到自己的最短路径 flag[s]1;dist[s]0;for(int j0;jnv;j){if(flag[j]0g[s][j]!INFdist[j](dist[s]g[s][j])){dist[j]dist[s]g[s][j];path[j]s;}}//确定其他点的最短路径for(int i1;inv;i){minnINF;for(int j0;jnv;j){if(flag[j]0dist[j]minn){minndist[j];kj;}}flag[k]1;for(int j0;jnv;j){if(flag[j]0g[k][j]!INFdist[j](dist[k]g[k][j])){dist[j]dist[k]g[k][j];path[j]k;}}}
}
int main()
{int x,y,w;scanf(%d %d,nv,ne);scanf(%d %d,s,end); // 初始化邻接矩阵for(int i0;inv;i)for(int j0;jnv;j){if(ij)g[i][j]g[j][i]0;else g[i][j]g[j][i]INF; } //建图for(int i0;ine;i){scanf(%d %d %d,x,y,w);g[x][y]g[y][x]w;} dijkstra(); printf(起点%d 到 终点%d 的最短路径的权值和为%d\n最短路径如下,s,end,dist[end]);printf(%d,end);int pend;while(path[p]!-1){printf(-%d,path[p]);ppath[p];} return 0;
} 4. 弗洛伊德算法
对于迪杰斯特拉算法中谈到的是如何解决图中任意两个顶点之间最短路径的计算问题迪杰斯特拉算法可以计算指定顶点到其他顶点之间的最短路径那么我就可以通过指定网络中的每一个顶点为源点重复执行迪杰斯特拉算法 n 次这样便可以得到每一对顶点之间的最短路径显然这种方式的时间复杂度为On^3 。Floyd算法时间复杂度也为On^3 但是她的实现比那种方式更加简洁优雅重要的是思想也很巧妙她就是弗洛伊德Floyd算法
迪杰斯特拉算法计算指定顶点到其他顶点之间的最短路径需要维护一个长度为 n 的辅助向量D。而弗洛伊德算法既然可以求得每一对顶点之间的最短路径自然要维护一个n*n 的二维辅助向量D同理也需要维护一个 nn 的二维路径向量 P。接下来你所看到的就是弗洛伊德算法最核心的部分了。现定义一个 n 阶方阵序列: 其中 我们图的邻接矩阵 : D(-1)
表示从顶点Vi到顶点Vj的中间顶点的序号不大于 1 的最短路径的长度; D(1)[i][j]
表示从顶点Vi到顶点Vj的中间顶点的序号不大于 k 的最短路径的长度 D(k)[i][j]
表示从顶点Vi到顶点Vj的最短路径的长度 D(n-1)[i][j]D(k)[i][j] 接下来让我们愉快的来看例子 我们先以上面包含三个顶点个无向图来讲解弗洛伊德算法的思想然后再使用在将迪杰斯特拉算法时用到的图上人脑模拟一遍
图中包含三个顶点的邻接矩阵的右上角标注的是 D^0,这是为什么呢不是说好的 n 阶方阵初始化为图的邻接矩阵吗 这就得感慨数学的严谨性质了除 n 阶方阵D^(-1)之外其他任何一个 n 阶方阵都可以使用它的前一个状态获得,则 故 n 阶矩阵D^-1和D^0是同一个矩阵。那么D^1如何求得呢当然是用她的前一个状态D^0求得了 比如计算顶点V0到V2的最短路径 其中 的值为5即顶点V0到顶点V2的直接距离为 5而 表示顶点V0到顶点V2经顶点V1中转以后的距离为4从而将 更新为4表示顶点V0到顶点V2的最短路径为4。
这就是弗洛伊德算法的精妙所在在一个图中要求得任意两个顶点Vi和Vj之间的最短路径我们则可以通过两个顶点Vi和Vj之间的顶点进行中转对于算法本身而言则是不断得尝试所有的中转结点从而确定两个顶点之间的最短路径。 根据公式计算完之后获得 n 阶矩阵D^1 4.1过程演示
为了更清楚弗洛伊德算法的执行过程和弗洛伊德算法的精妙所在我们以下图为例一步一步得脑子过一遍。 依旧用之前的图 算法第一步初始化 n 阶矩阵 D辅助向量 和n 阶矩阵P路径向量 第二步k 1此时 我们主要就是计算
其中
就是下方我们所标记的绿色列而
则表示我们所标记的绿色行。 这样我想大家就可以进行轻松计算了我们以取 i 0 为例进行计算则
分别与
所表示的绿色行中的每一个元素进行相加即得到 [2,1,4,8,6,1∞,1∞,1∞,1∞]然后与V0的行[0,1,5,∞,∞,∞,∞,∞,∞] 进行大小比较将更小值保留即得到 D(1)
中的V0行此时相应的只要将
更新为
红色表示被更新过的元素 第三步k 2 表示绿色一列 表示绿色的行。 0 i 8分别与 表示的绿色行进行运算并比较更新获得 D^2. 第四步k 3 表示绿色一列 表示绿色的行。0 i 8分别与表示的绿色行进行运算并比较更新从而获得 D^3. 第五步k 4 表示绿色一列 表示绿色的行。 0 i 8分别与
表示的绿色行进行运算并比较更新从而获得D^4 第六步k 5 表示绿色一列 表示绿色的行。 0 i 8分别与 表示的绿色行进行运算并比较更新从而获得D^5. 第七步k 6 表示绿色一列 表示绿色的行。 0 i 8分别与 表示的绿色行进行运算并比较更新从而获得D^6. 第八步k 7 表示绿色一列 表示绿色的行。 0 i 8分别与 表示的绿色行进行运算并比较更新从而获得D^7. 第九步k 8同样的道理进行计算我们注意到绿色区域划分出的左上角的区域都是不需要被更新的绿色区域本身也是不更新的所以 D^7与D^8 是一样的了 这样整个弗洛伊德算法的执行过程就结束了我知道看完可能还是有一点模糊不过我希望你能多看几遍这个例子最好是自己也和给你们绘制的图一样自己手工地人脑模拟一遍只有这样你才会真正理解算法的精妙所在
二.拓扑排序
1.基本概念
1.1什么是有向无环图
一个无环的有向图称为有向无环图简称 DAG 图。直接看图 图中最左边的是有向树中间的是有向无环图最右则的是有向图因为图中BED三个顶点之间构成一个有向环
1.2什么是活动
所有的工程或者某种流程都可以分为若干个小的工程或者阶段我们称这些小的工程或阶段为“活动”。打个比方如何把一只大象装到冰箱里很简单分三步。第一打开冰箱门第二将大象装进去第三关上冰箱门。这三步中的每一步便是一个 “活动”
1.3什么是AOV网
在一个表示工程的有向图中用顶点表示活动用弧表示活动之间的优先关系的有向图称为顶点表示活动的网简称AOV网。 日常生活中一项大的工程可以看作是由若干个子工程组成的集合这些子工程之间必定存在一定的先后顺序即某些子工程必须在其他的一些子工程完成后才能开始。 AOV网中的弧表示活动之间存在的某种制约关系比如上面说到将大象装入冰箱必须先打开冰箱门才能将大象装进去大象装进去才能关上冰箱门从而完成我们的任务。还有一个经典的例子那就是选课通常我们是学了C语言程序设计才能学习数据结构这里的制约关系就是课程之间的优先关系。
1.4什么是拓扑序列
设G(V,E)是一个具有n个顶点的有向图V中的顶点序列 V1,V2,V3.......Vn满足若从顶点Vi到Vj有一条路径则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列
1.5什么是拓扑排序
所以说所谓的拓扑排序其实就是对一个有向无环图构造拓扑序列的过程。当然这里的说法不够正式也是为了理解方便拓扑排序的官方定义是这样的 由某个集合上的一个偏序得到该集合上的一个全序的操作过程称为拓扑排序。
2.算法思想
拓扑排序的算法步骤很简单就是两步 (1) 在有向图中选一个没有前驱的顶点且输出之。 (2) 从图中删除该顶点和所有以它为尾的弧。 重复上述两步直至全部顶点均已输出或者当前图不存在无前驱的顶点为止后一种情况说明有向图中存在环。 为了清楚地理解拓扑排序思想我们分别采用有向无环图和有向有环图进行举例说明。
2.1有向无环图 第一步在有向图中选择一个没有前驱的顶点并输出观察图中的顶点发现顶点V1和顶点V6都是没有前驱的顶。假设我们先输出顶点V1当然也可以先输出V6从此处也就可以看出拓扑序列可以有多个 第二步从图中删除顶点V1和所有以它为尾的弧 之后的步骤就是重复一二两步我们接着看。 第三步在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为V6和顶点V3同样的道理我们可以选择这两个顶点的任何一个假设我们选择顶点V6 第四步删除顶点V6和所有以它为尾的弧 第五步在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为V4和顶点V3同样的道理我们可以选择这两个顶点的任何一个假设我们选择了顶点V4。删除顶点V4和所有以它为尾的弧 重复操作在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为V3。删除顶点V3和所有以它为尾的弧 在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为V2和 V5同样的道理我们可以选择这两个顶点的任何一个假设我们选择了顶点V2 。删除顶点V2和所有以它为尾的弧 在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为V5选择并输出此时所有的顶点均已经输出算法结束我们就得到了下图中的一个拓扑序列 整个过程便叫做拓扑排序
2.2有向有环图
其实过程和之前类似只是给大家提供一个思路如果面试官问你如何判断一个有向图中是否存在环时你应该第一反应想到的就是拓扑排序为什么拓扑排序可以判断一个有向图中是否存在环呢 第一步在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为A。删除顶点A和所有以它为尾的弧 第二步在有向图中选择一个没有前驱的顶点并输出图中没有前驱的顶点为C。删除顶点C和所有以它为尾的弧 第三步在有向图中选择一个没有前驱的顶点并输出发现当前图不存在无前驱的顶点但拓扑序列中并未输出所有的顶点所以剩下的顶点构成了环也证明了该有向图存在环
3.思想的实现
针对于拓扑排序思想篇提到的两步操作我们采用邻接表作为有向图的存储结构并且在头结点中增加一个存放顶点入度的数组。入度为零的顶点即为没有前驱的顶点删除顶点及以它为尾的弧的操作则可换以弧头顶点的入度减1来实现。 为了避免重复检查入度为零的顶点可另设一个栈暂存所有入度为领的顶点。 为了清晰地呈现拓扑排序的实现我们还是以上面提到的有向无环图为例子进行讲解。 图的邻接表表示 第一步遍历所有顶点将入度为0的顶点入栈即分别将顶点V1和顶点V6入栈 第二步弹出栈顶顶点V6并输出遍历顶点V6的邻接顶点即index 3 和 index 4 的顶点。将 index 3 的顶点V4的入度减 1 发现不为0则不入栈将 index 4 的顶点V5的入度减 1发现不为0则不入栈 第三步弹出栈顶顶点V1并输出然后遍历顶点V1的邻接顶点即 index 1index 2index 3的顶点。将 index 1 的顶点V2的入度减 1等于1 不为0则不入栈将 index 2的顶点V3的入度减 1等于0 则入栈将 index 3 的顶点V4的入度减 1等于0 则入栈 第四步弹出栈顶顶点V4并输出然后遍历顶点V4的邻接顶点即 index 4的顶点将 index 4 的顶点V5的入度减 1等于1 不为0则不入栈 第五步弹出栈顶顶点V3并输出然后遍历顶点V3的邻接顶点即 index 1 和 index 4 的顶点将 index 1 的顶点V2的入度减 1等于0 则入栈将 index 4 的顶点V5的入度减 1等于0 则入栈 第六步弹出栈顶顶点V5并输出顶点V5没有后继顶点 第七步弹出栈顶顶点V2并输出顶点V2没有后继顶点 #includestdio.h
#includestdlib.h
#define INF 65535
//链栈
typedef struct stackNode{int data;//存放入栈节点的下标struct stackNode *next;
}snode,*stack;
//初始化栈
stack inits(){stack s(snode*)malloc(sizeof(snode));s-nextNULL;return s;
}
//入栈函数
stack ppush(stack s,int e){snode* p(snode*)malloc(sizeof(snode));p-datae;p-nexts-next;s-nextp;return s;
}
//出栈--栈顶数据返回
stack ppop(stack s,int *e)
{if(s-nextNULL){(*e)-1;return s;}snode* ps-next;(*e)p-data;s-nextp-next;p-nextNULL;free(p);pNULL;return s;
}
//邻接表存有向图
//边单链表节点结构
typedef struct vNode{char d;struct edgeNode *first;
}Graph;
Graph g[105];
int n,m,ind[105];//入度
char topo[105];//保存拓朴序列
int find(char x){for(int i0;in;i){if(g[i].dx){return i;}}
}
int toposort(){stack sinits();for(int i0;in;i){if(ind[i]0){sppush(s,i);}}int e;//出栈的点的下标int k0;//topo数组的下标int flag0;for(int i1;in;i){sppop(s,e);if(e-1){printf(该图是带环图无拓扑序列\n);flag1;break;}topo[k]g[e].d;k;enode* pg[e].first;int j;while(p!NULL){jp-data;ind[j]--;if(ind[j]0)sppush(s,j);pp-next;}}if(flag0)return 1;elsereturn 0;
)
int main()
{scanf(%d %d,n,m);for(int i0;in;i){ getchar();scanf(%c,g[i].d);g[i].firstNULL;}char x,y;int xi,yi;for(int i0;im;i){getchar();scanf(%c %c,x,y);xifind(x);yifind(y);//统计入度ind[yi];enode* p(enode*)malloc(sizeof(enode));p-datayi;p-nextg[xi].first;g[xi].firstp; } int flagtoposort(); if(flag1){for(int i0;in;i){printf(%c ,topo[i]);} }printf(\n);return 0;
} 三.关键路径
1.基本概念
1.1AOE网
AOE网即边表示活动的网是与AOV网顶点表示活动相对应的一个概念。而拓扑排序恰恰就是在AOV网上进行的这是拓扑排序与关键路径最直观的联系。AOE网是一个带权的有向无环图其中顶点表示事件弧表示活动权表示活动持续的时间。下面的就是一个AOV网 其中V1V2V3.......V9表示事件a1.........a11表示活动活动的取值表示完成该活动所需要的时间如a1 6表示完成活动a1所需要的时间为6天。此外每一事件Vi表示在它之前的活动已经完成在它之后的活动可以开始如V5表示活动a4和a5已经完成活动a7和a8可以开始了
1.2AOE网的源点和汇点
由于一个工程中只有一个开始点和一个完成点故将AOE网中入度为零的点称为源点将出度为零的点称为汇点。 打个比方我们现在有一个工程就是将大象装进冰箱那么源点就相当于我们现在接到这样一个任务而汇点则表示我们完成了这个任务。那么我们之前所讲的打开冰箱门将大象装进去关上冰箱门就属于活动本身即a1....a11所表示的信息打开冰箱门所需要的时间就是活动所需要的时间而完成某一个活动所到达的顶点就表示一个事件冰箱门打开。下图中的红色顶点V1表示源点 V9表示汇点。
1.3什么是关键路径
举个例子。 唐僧师徒从长安出发去西天取经佛祖规定只有四人一起到达西天方能取得真经。假如师徒四人分别从长安出发走不同的路去西天孙悟空一个筋斗云十万八千里一盏茶的功夫就到了八戒和沙和尚稍慢点也就一天左右的时间而唐僧最慢需要14年左右。徒弟到达后是要等着师傅的。那么用时最长的唐僧所走的路就是取经任务中的关键路径。其他人走的路径属于非关键路径。由于AOE网中的有些活动是可以并线性进行的如活动a1、a2和a3就是可以并行进行的所以完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径就叫做关键路径。如下图中红色顶点和有向边构成的就是一条关键路径关键路径的长度就是完成活动 a1、a4和a9、a10所需要的时间总和即为 6192 18 1.4ETV
ETV事件最早发生时间就是顶点的最早发生时间 事件V2的最早发生时间表示从源点V1出发到达顶点V2经过的路径上的权值之和从源点V1出发到达顶点V2只经过了权值为6的边则V2的最早发生时间为6表示在活动a1完成之后事件V2才可以开始同理事件V6要发生即最早发生需要活动a3和活动a6完成之后才可以故事件V6的最早发生时间为 5 2 7。其他顶点事件的最早发生时间同理可的。需要说明事件的最早发生时间一定是从源点到该顶点进行计算的。
1.5LTV
LTV事件最晚发生时间就是每个顶点对应的事件最晚需要开始的时间如果超出此时间将会延误整个工期 前面在谈关键路径的概念时给出了一条上图中的关键路径该关键路径 V1V2V5 V7V9的长度为18为什么要提这个长度呢因为要计算某一个事件的最晚发生时间我们需要从汇点V9进行倒推。计算顶点V2的最晚发生时间为例已知关键路径的长度为18事件V2到汇点V9所需要的时间为 1 9 2 12则事件V2的最晚发生时间为18-12 6这时候我们发现这和事件V2的最早发生时间不是一样吗的确如此对于关键路径上的顶点都满足最早发生时间 etv 等于 最晚发生时间 ltv 的情况这也是我们识别关键活动的关键所在。再来计算一下事件V6的最晚发生时间事件V6到汇点V9所需要的时间为 4 4 8则事件V6的最晚发生时间为 18 - 8 10相当于说活动a6完成之后大可以休息3天再去完成活动a9也不会影响整个工期
1.6ETE
ETE活动的最早开工时间就是弧的最早发生时间 活动a4要最早开工时间为事件V2的最早发生时间 6同理活动a9的最早开工时间为事件v6的最早发生时间 7。显然活动的最早开工时间就是活动发生前的事件的最早开始时间
1.7LTE
LTE活动的最晚开工时间就是不推迟工期的最晚开工时间 活动的最晚开工时间则是基于事件的最晚发生时间。比如活动a4的最晚开工时间为事件V5的最晚发生时间减去完成活动a4所需时间即 7 - 1 6活动 a9的最晚开工时间为事件V8的最晚发生时间减去完成活动a9所需时间即 14 - 4 10 从上面也就可以看出 只要知道了每一个事件顶点的ETV 和 LTV就可以推断出对应的 ETE和 LTE . 此外还需要注意关键路径是活动的集合而不是事件的集合所以当我们求得 ETV 和LTV 之后还需要计算 ETE 和 LTE
2.关键路径算法
求关键路径的过程事实上最重要的就是上面提到的四个概念ETV、LTV、ETE 和 LTE求得了ETE与LTE之后只需要判断两者是否相等如果相等则为关键路径中的一条边则输出。为了清晰的明白算法的执行流程 首先求事件的最早发生事件ETV这里使用的就是之前分享的拓扑排序我们也走一遍算是对拓扑排序的回顾。 第一步建立图所对应的邻接表。 拓扑排序获得每一个事件的最早发生时间
初始时将ETV当中的数据都设置为0 下面开始便是拓扑排序的过程了。 第二步将入度为零的顶点V1入栈 第三步顶点V1出栈并遍历顶点V1的邻接顶点 即 index 分别为 123 的顶点V2、 V3和顶点V4 并将邻接顶点的入度减1判断是否为 0 如果为 0 则入栈。首先遍历 index 1 顶点V2 并将顶点V2的入度减 1 发现为零则将顶点V2入栈 判断 ETV[0] w(V1,V2) 是否大ETV[1] , 发现大于则将 ETV[1] 更新为 ETV[0] w(V1,V2) 6同理遍历 index 2 的顶点 V3 将顶点V3入栈并将ETV[2] 更新为 4 遍历 index 3 的顶点 V4 将顶点 V4入栈并将 ETV[3] 更新为 5 第四步弹出栈顶元素V4并遍历顶点V4的邻接顶点V6 . 将顶点V6的入度减一并将 ETV[5] 更新为 ETV[3] w(V4,V6)即为7. 第五步弹出栈顶元素 V6 并遍历邻接顶点V8 第六步弹出栈顶元素 V3并遍历V3 的邻接顶点V5 第七步弹出栈顶元素V2,并遍历V2的邻接顶点V5 第八步弹出栈顶元素V5 ,并遍历V5的邻接顶点V7和V8 第九步弹出栈顶元素 V8,并遍历V8的邻接顶点V9 第十步弹出栈顶元素V7 ,并遍历V7的邻接顶点V9 第十一步将栈顶元素V9出栈 其中我们将拓扑排序过程中的出栈序列依次入栈即拓扑排序结束时我们响应的保存了一个 出栈序列V1 V4 V6 V3 V2 V5 V8 V7 V9用于逆向计算事件的最晚发生时间 根据事件的最早发生时间ETV推断事件的最晚发生时间 LTV 通过拓扑排序我们获得了每一个顶点的最早发生时间 ETV紧接着便可以计算 LTV了。 计算LTV的值即每一个顶点的最晚发生时间值初始时将LTV的值初始化为汇点V9的时间 18 紧接着则是访问之前的出栈序列栈 。 首先将顶点V9出栈什么都不做 第二步将顶点V7出栈并判断LTV[6] 与 LTV[8] - w(V7,V9)的大小将 LTV 更新为 LTV[8] -w(V7,V9) 16 第三步将顶点V8出栈更新 LTV[7] 为 LTV[8] - w(V8,V9) 14 第四步将顶点V5 出栈并遍历V5的邻接顶点V7和V8。用邻接顶点V7的LTV值减去活动a7值并与顶点V5的LTV值进行比较将LTV[4] 更新为 7同理用邻接顶点V8的LTV值减去活动a8的值并与V5顶点的值进行比较发现相等不做更新 第五步弹出栈顶元素V2 ,并遍历 V2的邻接顶点V5 , 用顶点V5的LTV(最晚发生时间) 减去活动a4所需时间即为6将顶点V2的LTV[1] 更新为6 第六步弹出栈顶事件顶点V3 ,并更新顶点V3的最晚发生时间 第七步弹出栈顶事件V6顶点 第八步弹出栈顶元素V4并更新其最晚发生时间 第九步弹出栈顶元素V1并更新其最晚发生时间。使用事件V2的最晚发生时间 6 减去活动a1所需时间6等于0与顶点V1的最晚时间相比较并更新为0。需要说明事实上源点的最晚发生时间与最早发生时间都为0毋庸置疑 此时我们得到每个事件顶点的最早发生时间和最晚发生时间但关键路径是活动的集合所以接下来我们用事件的最早发生时间和最晚发生时间计算出活动弧的最早与最晚发生时间即可 计算活动的最早与最晚开工时间 第一步从源点V1开始遍历源点的邻接顶点 V2, 将弧 V1,V2 上的活动a1 的最早发生时间更新为源点 V1的最早发生时间 0将活动a1 的最晚发生时间更新为事件V2的最晚发生时间 6 减去活动 a1所需要的时间6即为0. 判断活动a1的最早发生时间与最晚发生时间是否相等如果相等则为关键活动并输出。同理遍历源点v1的邻接顶点v3和v4并更新弧a2和a3的最晚开工时间与最早开工时间 第二步访问顶点 V2遍历V2的邻接顶点V5 . 将活动a4的最早发生时间更新为事件 V2的最早发 生时间将活动 a4的最晚发生时间更新为事件 V5的最晚发生时间 7 减去活动 a4 所需时间 1即为6 第三步访问顶点V3遍历V3的邻接顶点V5 . 将活动a5的最早发生时间更新为事件V3的最早发生时间 4 将活动a5的最晚发生时间更新为事件V5的最晚发生时间 7 减去活动a5所需时间 1即为6. 第四步访问顶点V4遍历该顶点的邻接顶点V6 将活动a6的最早发生时间更新为事件V4的最 早发生时间5活动a6的最晚发生时间为事件V6的最晚发生时间10 减去 活动 a6 所需要的时间 2即为8. 第五步访问顶点 V5并分别遍历该顶点的邻接顶点V7 和顶点 V8。将活动a7和a8的最早发生时 间更新为时间V5的最早发生时间7最晚发生时间也更新为7 第六步访问顶点V6并遍历该顶点的邻接顶点 V8将活动a9的最早发生时间更新为事件V6 的 最早发生时间7最晚发生时间更新为事件V8的最晚发生时间 14 减去活动a9所需时间4 即为10. 第七步访问顶点 V7更新活动 a10的最早发生时间和最晚发生时间 第八步访问顶点V8 更新活动 a11的最早发生时间和最晚发生时间 第九步访问顶点V9 没有邻接顶点什么都不做 #includestdio.h
#includestdlib.h
#define INF 65535
//链栈
typedef struct stackNode{int data;//存放入栈节点的下标struct stackNode *next;
}snode,*stack;
//初始化
stack inits(){stack s(snode*)malloc(sizeof(snode));s-nextNULL;return s;
}
//入栈函数
stack ppush(stack s,int e)
{snode* p(snode*)malloc(sizeof(snode));p-datae;p-nexts-next;s-nextp;return s;}
//出栈--栈顶数据返回
stack ppop(stack s,int *e)
{if(s-nextNULL){(*e)-1;return s;} snode* ps-next;(*e)p-data;s-nextp-next;p-nextNULL;free(p);pNULL; return s;}
//------------------------
//邻接表存带权有向图----- AOE网
//边单链表节点结构
typedef struct edgeNode
{int data;//存放入栈节点的下标struct edgeNode *next;int w;//1.边权
}enode;
//顶点数组
typedef struct vNode
{char d;struct edgeNode *first;
}Graph;
Graph g[105];
int n,m;
int ind[105];//入度
int etv[105];//事件的最早发生时间
int ltv[105];//事件的最晚发生时间
//char topo[105];//保存拓扑序列
int topo[105];//保存拓扑序列----基于顶点下标
int find(char x)
{for(int i0;in;i){if(g[i].dx){return i;}}
}
void toposort()
{stack sinits();//初始化栈 for(int i0;in;i){//初始化etv数组 etv[i]0;} for(int i0;in;i){if(ind[i]0){sppush(s,i);}}int e;//出栈的点的下标int k0;//topo数组的下标; int flag0;for(int i1;in;i){sppop(s,e);topo[k]e;//出栈的顶点的下标 保存在topo序列里面 k;enode* pg[e].first;int j;while(p!NULL){jp-data;//j就是e的出边邻接点 e----j if(etv[j](etv[e]p-w)){//求etv etv[j]etv[e]p-w;}ind[j]--;if(ind[j]0){sppush(s,j);}pp-next;} }
}
void CriticalPath()
{int endtopo[n-1];//0 ~~ n-1for(int i0;in;i){
//初始化ltv,将每个点的最晚发生时间都初始化成终点的最早发生时间即可 ltv[i]etv[end];}int x;//逆拓扑序 更新ltv for(int in-2;i0;i--){xtopo[i];//x点的最晚发生时间enode* pg[x].first;while(p!NULL){int jp-data;//x--jif(ltv[x](ltv[j]-p-w)){ltv[x]ltv[j]-p-w;}pp-next;}} printf(以下是关键活动\n);//遍历所有的边求每个边的ete lteint ete,lte;for(int i0;in;i){for(enode* pg[i].first;p!NULL;pp-next){int jp-data;///i---j eteetv[i];lteltv[j]-p-w;if(etelte){printf(%c %c\n,g[i].d,g[j].d);}} } }
int main()
{scanf(%d %d,n,m);for(int i0;in;i){ getchar();scanf(%c,g[i].d);g[i].firstNULL;}char x,y;int xi,yi,wi;for(int i0;im;i){getchar();scanf(%c %c %d,x,y,wi);xifind(x);yifind(y);//统计入度ind[yi];enode* p(enode*)malloc(sizeof(enode));p-datayi;p-wwi;//p-nextg[xi].first;g[xi].firstp; }toposort(); CriticalPath();return 0;
} 总结
toposort为关键路径服务关键路径代码较难需要一些时间消化
