【图的应用四：关键路径】- 用 C 语言实现关键路径

目录

一、AOE-网

二、算法的实现

2.1 - ALGraph.h

2.2 - ALGraph.c

2.3 - Test.c

 

一、AOE-网

与 AOV-网相对应的是 AOE-网（Activity On Edge），即以边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件、弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。

例如，下图所示为一个有 11 项活动的 AOE-网。其中有 9 个事件 v0, v1, ..., v8，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。例如，v0 表示整个工程开始，v8 表示整个过程结束，v4 表示 a4 和 a5 已经完成，a7 和 a8 可以开始了。与每个活动相联系的数是执行该活动所需的时间，比如，活动 a1 需要 6 天，a2 需要 4 天等。

AOE-网在工程计划和经营管理中有广泛的应用，针对实际的应用问题，通常需要解决以下两个问题：

  1. 估算完成整项工程至少需要多少时间。

  2. 判定哪些活动是影响工程进度的关键。

工程进度控制的关键在于抓住关键活动。在一定范围内，非关键活动的提前完成对于整个工程的进度没有直接的好处，它的稍许拖延也不会影响整个工程的进度。工程的指挥者可以把非关键活动的人力和物力资源暂时调给关键活动，加速其进展，以使整个工程提前完工。

由于整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下，网中只有一个入度为零的点，称作源点，也只有一个出度为零的点，称作汇点。在 AOE-网中，一条路径各弧上的权值之和称为该路径的带权路径长度（后面简称路径长度）。要估算整项工程完成的最短时间，就是要找一条从源点到汇点的带权路径长度最长的路径，称为关键路径。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键，它们的提前或拖延使整个工程提前或拖延。

例如，在上图中，v0 是源点，v8 是汇点，关键路径有两条：(v0, v1, v4, v6, v8) 和 (v0, v1, v4, v7, v8)，长度均为 18，关键活动为 (a1, a4, a7, a10) 和 (a1, a4, a8, a11)。比如，关键活动 a1 需要 6 天完成，如果 a1 提前 1 天，整个工程也可以提前 1 天完成。所以不论估算工期，还是研究如何加快工程进度，主要问题就在于要找到 AOE-网的关键路径。

如何确定关键路径，首先定义 4 个描述量。

  1. 事件 vi 的最早发生时间 ve(i)：

    进入事件 vi 的每一活动都结束，vi 才可发生，所以 ve(i) 是从源点到 vi 的最长路径长度。

    求 ve(i) 的值，可根据拓扑顺序从源点开始向汇点递推。通常将工程的开始顶点事件 v0 的最早发生时间定义为 0，即：ve(0) = 0 \\ ve(i) = Max\{ ve(k) + w_{k,i} \} <v_k, v_i> \in T, 1 \le i \le n-1

    其中，T 是所有以 vi 为头的弧的集合，w_{k, i} 是弧 <vk, vi> 的权值，即对应活动 <vk, vi> 的持续时间。

  2. 事件 vi 的最迟发生事件 vl(i)：

    事件 vi 的发生不得延误 vi 的每一后继事件的最迟发生事件。为了不拖延工期，vi 的最迟发生时间不得迟于其后继事件 vk 的最迟发生事件减去活动 <vi, vk> 的持续事件。

    求出 ve(i) 后，可根据逆拓扑顺序从汇点开始向源点递推，求出 vl(i)。vl(n-1) = ve(n-1) \\ vl(i) = Min\{ vl(k) - w_{i, k} \} <v_i, v_k> \in S, 0 \le i \le n-2

    其中，S 是所有以 vi 为为的弧，w_{i, k} 是弧 <vi, vk> 的权值。

  3. 活动 ai = <vj, vk> 的最早开始时间 ae(i)：

    只有事件 vj 发生了，活动 ai 才能开始，所以活动 ai 的最早开始时间等于事件 vj 的最早发生时间 ve(j)，即：ae(i) = ve(j)

  4. 活动 ai = <vj, vk> 的最晚开始时间 al(i)：

    活动 ai 的开始时间需保证不延误事件 vk 的最迟发生时间。所以活动 ai 的最晚开始时间 al(i) 等于事件 vk 的最迟发生时间 vl(k) 减去活动 ai 的持续时间 w_{j, k}，即：al(i) = vl(k) - w_{j, k}

显然，对于关键活动而言，ae(i) = al(i)。对于非关键活动，al(i) - ae(i) 的值是该工程的期限余量，在此范围内的适度延误不会影响整个工程的工期。

二、算法的实现

由于每个事件的最早发生时间 ve(i) 和最迟发生时间 vl(i) 要在拓扑序列的基础上进行计算，所以关键路径算法的实现要基于拓扑排序算法，我们仍采用邻接表做有向图的存储结构。

2.1 - ALGraph.h

#pragma once

#include <stdbool.h>

typedef int ArcType;
typedef char VertexType;

#define DEFAULT_CAPACITY 2

typedef struct ArcNode
{
	int adjVexPos;
	struct ArcNode* nextArc;
	ArcType weight;
}ArcNode;

typedef struct VertexNode
{
	VertexType vertex;
	ArcNode* firstArc;
}VertexNode;

typedef struct ALGraph
{
	VertexNode* vertices;
	int vSize;
	int aSize;
	int capacity;
}ALGraph;

void ALGraphInit(ALGraph* pg);

void ShowAdjList(ALGraph* pg);

int GetVertexPos(ALGraph* pg, VertexType v);

void InsertVertex(ALGraph* pg, VertexType v);
void InsertArc(ALGraph* pg, VertexType v1, VertexType v2, ArcType weight);

void ALGraphDestroy(ALGraph* pg);

// 拓扑排序
bool TopologicalSort(ALGraph* pg, int* topo);

// 关键路径
void CriticalPath(ALGraph* pg);

2.2 - ALGraph.c

#include "ALGraph.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "Stack.h"

void ALGraphInit(ALGraph* pg)
{
	assert(pg);
	pg->vSize = pg->aSize = 0;
	pg->capacity = DEFAULT_CAPACITY;

	pg->vertices = (VertexNode*)malloc(sizeof(VertexNode) * pg->capacity);
	assert(pg->vertices);
	for (int i = 0; i < pg->capacity; ++i)
	{
		pg->vertices[i].firstArc = NULL;
	}
}

void ShowAdjList(ALGraph* pg)
{
	assert(pg);
	for (int i = 0; i < pg->vSize; ++i)
	{
		printf("%d %c:>", i, pg->vertices[i].vertex);
		ArcNode* cur = pg->vertices[i].firstArc;
		while (cur)
		{
			printf("%d-->", cur->adjVexPos);
			cur = cur->nextArc;
		}
		printf("NULL\n");
	}
}

int GetVertexPos(ALGraph* pg, VertexType v)
{
	assert(pg);
	for (int i = 0; i < pg->vSize; ++i)
	{
		if (pg->vertices[i].vertex == v)
			return i;
	}
	return -1;
}

void InsertVertex(ALGraph* pg, VertexType v)
{
	assert(pg);
	if (pg->vSize == pg->capacity)
	{
		VertexNode* tmp = (VertexNode*)realloc(pg->vertices, sizeof(VertexNode) * 2 * pg->capacity);
		assert(tmp);
		pg->vertices = tmp;
		for (int i = pg->capacity; i < 2 * pg->capacity; ++i)
		{
			pg->vertices[i].firstArc = NULL;
		}
		pg->capacity *= 2;
	}
	pg->vertices[pg->vSize++].vertex = v;
}

void InsertArc(ALGraph* pg, VertexType v1, VertexType v2, ArcType weight)
{
	assert(pg);
	int pos1 = GetVertexPos(pg, v1);
	int pos2 = GetVertexPos(pg, v2);
	if (pos1 == -1 || pos2 == -1)
		return;

	// 插入 <v1, v2>
	ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
	assert(p);
	p->adjVexPos = pos2;
	p->weight = weight;
	// 头插
	p->nextArc = pg->vertices[pos1].firstArc;
	pg->vertices[pos1].firstArc = p;

	++pg->aSize;
}

void ALGraphDestroy(ALGraph* pg)
{
	assert(pg);
	for (int i = 0; i < pg->vSize; ++i)
	{
		ArcNode* cur = pg->vertices[i].firstArc;
		while (cur)
		{
			// 头删
			pg->vertices[i].firstArc = cur->nextArc;
			free(cur);
			cur = pg->vertices[i].firstArc;
		}
	}
	free(pg->vertices);
	pg->vertices = NULL;

	pg->vSize = pg->aSize = pg->capacity = 0;
}

// 拓扑排序
bool TopologicalSort(ALGraph* pg, int* topo)
{
	assert(pg);
	int* indegree = (int*)malloc(sizeof(int) * pg->vSize);
	assert(indegree);
	for (int i = 0; i < pg->vSize; ++i)
	{
		indegree[i] = 0;
	}
	for (int i = 0; i < pg->vSize; ++i)
	{
		ArcNode* cur = pg->vertices[i].firstArc;
		while (cur)
		{
			++indegree[cur->adjVexPos];
			cur = cur->nextArc;
		}
	}

	Stack st;
	StackInit(&st);
	for (int i = 0; i < pg->vSize; ++i)
	{
		if (indegree[i] == 0)
			StackPush(&st, i);
	}

	int cnt = 0;
	while (!StackEmpty(&st))
	{
		int i = StackTop(&st);
		StackPop(&st);
		topo[cnt++] = i;

		ArcNode* cur = pg->vertices[i].firstArc;
		while (cur)
		{
			if (--indegree[cur->adjVexPos] == 0)
				StackPush(&st, cur->adjVexPos);
			cur = cur->nextArc;
		}
	}
	StackDestroy(&st);

	if (cnt == pg->vSize)
		return true;
	else
		return false;
}

// 关键路径
void CriticalPath(ALGraph* pg)
{
	assert(pg);
	int* topo = (int*)malloc(sizeof(int) * pg->vSize);
	assert(topo);
	if (!TopologicalSort(pg, topo))
	{
		printf("网中存在有向环！\n");
		free(topo);
		return;
	}

	int* ve = (int*)malloc(sizeof(int) * pg->vSize);
	int* vl = (int*)malloc(sizeof(int) * pg->vSize);
	assert(ve && vl);

	for (int i = 0; i < pg->vSize; ++i)
	{
		ve[i] = 0;
	}
	// 按照拓扑顺序求每个事件的最早发生时间
	for (int i = 0; i < pg->vSize - 1; ++i)
	{
		int k = topo[i];
		ArcNode* cur = pg->vertices[k].firstArc;
		while (cur)
		{
			if (ve[k] + cur->weight > ve[cur->adjVexPos])
				ve[cur->adjVexPos] = ve[k] + cur->weight;
			cur = cur->nextArc;
		}
	}

	for (int i = 0; i < pg->vSize; ++i)
	{
		vl[i] = ve[topo[pg->vSize - 1]];
	}
	// 按照逆拓扑顺序求每个事件的最迟发生时间
	for (int i = pg->vSize - 2; i >= 0; --i)
	{
		int k = topo[i];
		ArcNode* cur = pg->vertices[k].firstArc;
		while (cur)
		{
			if (vl[cur->adjVexPos] - cur->weight < vl[k])
				vl[k] = vl[cur->adjVexPos] - cur->weight;
			cur = cur->nextArc;
		}
	}

	// 判定每一活动是否为关键活动
	for (int i = 0; i < pg->vSize; ++i)
	{
		ArcNode* cur = pg->vertices[i].firstArc;
		while (cur)
		{
			int ae = ve[i];
			int al = vl[cur->adjVexPos] - cur->weight;
			if (ae == al)
				printf("<%c, %c> 是关键活动\n", pg->vertices[i].vertex, pg->vertices[cur->adjVexPos].vertex);
			cur = cur->nextArc;
		}
	}

	free(topo);
	free(ve);
	free(vl);
}

2.3 - Test.c

#include "ALGraph.h"
#include <stdio.h>

int main()
{
	ALGraph g;
	ALGraphInit(&g);
	InsertVertex(&g, 'A');
	InsertVertex(&g, 'B');
	InsertVertex(&g, 'C');
	InsertVertex(&g, 'D');
	InsertVertex(&g, 'E');
	InsertVertex(&g, 'F');
	InsertVertex(&g, 'G');
	InsertVertex(&g, 'H');
	InsertVertex(&g, 'I');
	InsertArc(&g, 'A', 'B', 6);
	InsertArc(&g, 'A', 'C', 4);
	InsertArc(&g, 'A', 'D', 5);
	InsertArc(&g, 'B', 'E', 1);
	InsertArc(&g, 'C', 'E', 1);
	InsertArc(&g, 'D', 'F', 2);
	InsertArc(&g, 'E', 'G', 9);
	InsertArc(&g, 'E', 'H', 7);
	InsertArc(&g, 'F', 'H', 4);
	InsertArc(&g, 'G', 'I', 2);
	InsertArc(&g, 'H', 'I', 4);
	ShowAdjList(&g);
	printf("\n");

	CriticalPath(&g);

	ALGraphDestroy(&g);
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/267127.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SpringSecurity深度解析与实践（3）

SpringSecurity深度解析与实践（3）

这里写自定义目录标题 引言SpringSecurity之授权授权介绍java权限集成 登录失败三次用户上锁 引言 SpringSecurity深度解析与实践&#xff08;2&#xff09;的网址 SpringSecurity之授权 授权介绍 Spring Security 中的授权分为两种类型&#xff1a; 基于角色的授权&#…
阅读更多...
电视技巧：分享7个小米电视使用技巧，你都知道吗

电视技巧：分享7个小米电视使用技巧，你都知道吗

小米电视&#xff0c;采用49英寸4K屏幕以及独立外置音响。而作为一款智能产品&#xff0c;小米电视自带的MIUI TV系统也一直不断更新优化&#xff0c;根据大多数用户的意愿增添了很多更加人性化、更加方便的功能。不过可能很多入手的用户很还都并不十分了解&#xff0c;因此在这…
阅读更多...
04_线性表

04_线性表

线性表 顺序表顺序表的实现顺序表的遍历顺序表的容量可变顺序表的时间复杂度java中ArrayList实现 链表单向链表单向链表API设计java中LinkedList实现 链表的复杂度分析链表反转快慢指针中间值问题单向链表是否有环问题有环链表入口问题 循环链表约瑟夫问题 栈栈概述生活中的栈计…
阅读更多...
深度学习数据处理（一）

深度学习数据处理（一）

在PyTorch中&#xff0c;torch.Tensor是存储和变换数据的主要工具。如果你之前用过NumPy&#xff0c;你会发现Tensor和NumPy的多维数组非常类似。然而&#xff0c;Tensor提供GPU计算和自动求梯度等更多功能&#xff0c;这些使Tensor更加适合深度学习。 张量&#xff08;tensor&…
阅读更多...
Python使用多线程解析超大日志文件

Python使用多线程解析超大日志文件

目录 一、引言 二、多线程基本概念 三、Python中的多线程实现 四、使用多线程解析超大日志文件 五、性能优化和注意事项 总结 一、引言 在处理大量数据时&#xff0c;单线程处理方式往往效率低下&#xff0c;而多线程技术可以有效地提高处理速度。Python提供了多种多线程…
阅读更多...
算法模板之队列图文详解

算法模板之队列图文详解

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;算法模板、数据结构 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. ⛳️模拟队列1.1 &#x1f514;用数组模拟实现队列1.1.1 &#x1f47b;队列的定…
阅读更多...
实习知识整理6：前后端利用ajax数据传输的四种方式

实习知识整理6：前后端利用ajax数据传输的四种方式

方式1&#xff1a;前端发送key/value(String字符串)&#xff0c;后台返回文本 前端&#xff1a; <input id"test1" type"button" value"前端发送key/value(String字符串)&#xff0c;后台返回文本"/> $(function() {$("#test1&quo…
阅读更多...
LaTex详细安装及配置（Windows）

LaTex详细安装及配置（Windows）

文章目录 引言LaTeX简介优势与应用领域 安装环境安装texlive下载texlive安装 编辑器安装texstudio下载texstudio安装 环境配置 使用第一个LaTex文档新建文件编程查看 效果 结语 引言 在当今信息技术高度发达的时代&#xff0c;文档的编辑和排版是我们日常工作和学习中不可或缺…
阅读更多...
深入了解TypeChat

深入了解TypeChat

在过去的几个月里&#xff0c;我们看到了最新一波大型语言模型的热潮。虽然聊天助手是最直接的应用程序&#xff0c;但如何最好地将这些模型集成到现有的应用程序界面中仍是一个大问题。 换句话说&#xff0c;我们如何用自然语言界面增强传统UI ? 我们如何使用人工智能来接受…
阅读更多...
ctfshow中web入门第web41

ctfshow中web入门第web41

ctfshow中web入门第web41 ​​ 留下了|运算绕过的方法那么直接利用脚本即可。 先用or运算的php脚本生成需要的规则文件(.txt文件)。如下图直接把需要绕过的正则替换成题目的正则就好&#xff1a; ​​ 再用python脚本基于刚刚生成的txt文件跑出payload&#xff0c;如下图&…
阅读更多...
9.独立看门狗IWDG窗口看门狗WWDG编码思路

9.独立看门狗IWDG窗口看门狗WWDG编码思路

前言&#xff1a; 看门狗是维护系统稳定性的一向技术&#xff0c;可以让代码跑飞及时复位&#xff0c;在产品中非常常用&#xff0c;俗话说&#xff0c;重启能解决90%的问题&#xff0c;作为产品来说&#xff0c;你总不能因为一次bug就让程序卡死不动了&#xff0c;肯定要试着重…
阅读更多...
消息队列之关于如何实现延时队列

消息队列之关于如何实现延时队列

一、延时队列的应用 1.1 什么是延时队列&#xff1f; 顾名思义&#xff1a;首先它要具有队列的特性&#xff0c;再给它附加一个延迟消费队列消息的功能&#xff0c;也就是说可以指定队列中的消息在哪个时间点被消费。 延时队列在项目中的应用还是比较多的&#xff0c;尤其像…
阅读更多...
2024年值得关注的十大TS项目

2024年值得关注的十大TS项目

探索未来&#xff1a;用无/低代码工具和人工智能创新重塑2024年的十大TS项目 再过几天&#xff0c;2023年就要结束了&#xff0c;我们即将迎来2024年。2023年是人工智能技术快速发展的一年&#xff0c;人工智能应用激增。人工智能技术的飞速发展给我们的生活和工作带来了巨大的…
阅读更多...
CreateProcess error=216, 该版本的 %1 与你运行的 Windows 版本不兼容。请查看计算机的系统信息，然后联系软件发布者。

CreateProcess error=216, 该版本的 %1 与你运行的 Windows 版本不兼容。请查看计算机的系统信息，然后联系软件发布者。

第一个go程序就出错了&#xff0c;错误提示&#xff1a; Error running ‘go build hello.go’: Cannot run program “C:\Users\Administrator\AppData\Local\Temp___go_build_hello_go.exe” (in directory “G:\go\workspace”): CreateProcess error216, 该版本的 %1 与你运…
阅读更多...
【React Native】第一个Android应用

【React Native】第一个Android应用

第一个Android应用 环境TIP开发工具环境及版本要求建议官方建议 安装 Android Studio首次安装模板选择安装 Android SDK配置 ANDROID_HOME 环境变量把一些工具目录添加到环境变量 Path[可选参数] 指定版本或项目模板 运行使用 Android 模拟器编译并运行 React Native 应用修改项…
阅读更多...
2023-强网杯-【强网先锋-ez_fmt】

2023-强网杯-【强网先锋-ez_fmt】

文章目录 ez_fmt libc-2.31.so检查main思路exp 参考链接 ez_fmt libc-2.31.so 检查 没有地址随机化 main 简单粗暴的printf格式化字符串漏洞 思路 泄露地址&#xff0c;覆盖返回地址形成ROP链 printf执行时栈上存在__libc_start_main243的指令的地址&#xff0c;可以泄露…
阅读更多...
C/C++ 基础函数

C/C++ 基础函数

memcpy&#xff1a;C/C语言中的一个用于内存复制的函数&#xff0c;声明在 string.h 中&#xff08;C是 cstring&#xff09; void *memcpy(void *destin, void *source, unsigned n);作用是&#xff1a;以source指向的地址为起点&#xff0c;将连续的n个字节数据&#xff0c;…
阅读更多...
全国(山东、安徽)职业技能大赛--信息安全管理与评估大赛题目+答案讲解

全国(山东、安徽)职业技能大赛--信息安全管理与评估大赛题目+答案讲解

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏…
阅读更多...
Python算法例25 落单的数Ⅲ

Python算法例25 落单的数Ⅲ

1. 问题描述 给出2n2个非负整数元素的数组&#xff0c;除其中两个数字之外&#xff0c;其他每个数字均出现两次&#xff0c;找到这两个数字。 2. 问题示例 给出[1&#xff0c;2&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;4&#xff0c;5&#xff0c;3]&#xff0c…
阅读更多...
dubbo线程池为什么耗尽

dubbo线程池为什么耗尽

文章概述 大家可能都遇到过DUBBO线程池打满这个问题&#xff0c;报错如下&#xff0c;本文我们就一起分析DUBBO线程池打满这个问题。 cause: org.apache.dubbo.remoting.RemotingException: Server side(10.0.0.100,20881) thread pool is exhausted, detail msg:Thread pool …
阅读更多...
最新文章

Copyright @ 2022~2023