AOE关键路径求解

题目8：关键路径算法的实现
要求：输入一个表示工程活动关系的AOV网，输出其关键路径，并给出完成该工程所需的最短时间。
实现代码

# include <stdio.h>
# include <stdlib.h>

#define OK 1
#define ERROR 0
#define MVNum 100
 
typedef int Status;
typedef char VerTexType;
typedef int OtherInfo;
int Len=0;
typedef struct StackNode{
	int data;  
	StackNode *next;   
}StackNode, *StackList;  //栈结构
 
typedef struct ArcNode{
	int adjvex;        //邻接点编号
	ArcNode *nextarc;  //指向下一个边节点
	OtherInfo weight;  //边节点的权值
}ArcNode;              //边节点类型
 
typedef struct VNode{
	VerTexType data;   //顶点的信息
	ArcNode *firstarc; //指向第一个边界点
}VNode, AdjList[MVNum];//头节点类型
 
typedef struct{
	AdjList vertices;  //邻接表的头节点数组
	int vexnum, arcnum;//图的顶点数和边数
}ALGraph;              //完整的图的邻接表结构

int indegree[MVNum] = { 0 };
 

//寻找顶点位置
int LocateVex(ALGraph *G, VerTexType v);
//创建AOE工程网络
void CreateUDG(ALGraph *G);
//拓扑排序算法
Status TopologicalSort(ALGraph G, int *topo);
//寻找并输出关键路径
Status CriticalPath(ALGraph G);


StackList InitStack(StackList &S)
{
	S = NULL;
	return S;
}
 
StackList Push(StackList S, int e)
{
	StackList p;
	p = (StackNode *)malloc(sizeof(StackNode));
	p->data = e;
	p->next = S;
	S = p;
	return S;
}
 
StackList Pop(StackList S, int *e)
{
	StackList p;
	p = S;
	if (!p)
		return ERROR;
	*e = p->data;
	S = S->next;
	free(p);
	return S;
}

//寻找顶点位置
int LocateVex(ALGraph *G, VerTexType v)
{
	int i;
	for (i = 0; i < (G->vexnum); i++)
	{
		if (v == G->vertices[i].data)
			return i;
	}
}
//创建AOE工程网络
void CreateUDG(ALGraph *G)
{
	int i, j, k;
	OtherInfo w;
	VerTexType v1, v2;
	ArcNode *p1;
	printf("输入总节点数和总边数：");
	scanf("%d %d", &G->vexnum, &G->arcnum);
	fflush(stdin);
	printf("输入各个节点的值：");
	for (i = 0; i < G->vexnum; i++)
	{
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].firstarc = NULL;
	}
	for (k = 0; k < G->arcnum; k++)
	{
		fflush(stdin);
		printf("输入一条边的两个节点以及边的权值：");
		scanf("%c %c %d", &v1, &v2, &w);
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		p1 = (ArcNode *)malloc(sizeof(ArcNode));
		p1->adjvex = j;
		p1->weight = w;
		p1->nextarc = G->vertices[i].firstarc;
		G->vertices[i].firstarc = p1;
		indegree[j]++;
	}
}
//拓扑排序算法
Status TopologicalSort(ALGraph G, int *topo)
{
	int i, m, k;
	StackList S;
	ArcNode *p;
	S = NULL;
	for (i = 0; i < G.vexnum; i++)
	{
		if (!indegree[i])
			S = Push(S, i);
	}
	m = 0;
	while (S)
	{
		S = Pop(S, &i);
		topo[m] = i;
		++m;
		p = G.vertices[i].firstarc;
		while (p != NULL)
		{
			k = p->adjvex;
			--indegree[k];
			if (indegree[k] == 0)
				S = Push(S, k);
			p = p->nextarc;
		}
	}
	topo[m] = -1;
	if (m < G.vexnum)
		return ERROR;
	else
		return OK;
}
//寻找并输出关键路径
Status CriticalPath(ALGraph G)
{
	int i, j, k, e, l, o;
	int *ve, *vl;
	int topo[MVNum];
	ArcNode *p;
	ve = (int *)malloc(sizeof(int)*G.vexnum);
	vl = (int *)malloc(sizeof(int)*G.vexnum);
	if (!TopologicalSort(G, topo))
		return ERROR;
	else 
	    printf("关键路径如下：\n");

	for (i = 0; i < G.vexnum; i++)
		ve[i] = 0;
	for (i = 0; i < G.vexnum; i++)
	{
		k = topo[i];
		p = G.vertices[k].firstarc;
		while (p)
		{
			j = p->adjvex;
			if (ve[j] < ve[k] + p->weight)
				ve[j] = ve[k] + p->weight;
			p = p->nextarc;
		}
	}
	for (i = 0; i < G.vexnum; i++)
		vl[i] = ve[G.vexnum - 1];
	for (i = G.vexnum - 1; i >= 0; i--)
	{
		k = topo[i];
		p = G.vertices[k].firstarc;
		while (p)
		{
			j = p->adjvex;
			if (vl[k]>vl[j] - p->weight)
				vl[k] = vl[j] - p->weight;
			p = p->nextarc;
		}
	}
	for (i = 0; i < G.vexnum; i++)
	{
		p = G.vertices[i].firstarc;
		while (p)
		{
			j = p->adjvex;
			e = ve[i];
			l = vl[j] - p->weight;
			if (e == l){
				printf("%c->%c\n", G.vertices[i].data, G.vertices[j].data);
                o=G.vertices[i].firstarc->weight;//Len += e;//G.vertices[i].firstarc->weight
			}
			p = p->nextarc;
		}
	}
	Len= e + o;
	return OK;
}

int main(void)
{
	ALGraph G;
	CreateUDG(&G);
	if (!CriticalPath(G))
		printf("错误\n");
	else{
        printf("路径长度是%d\n",Len);
		printf("结束\n");
	}
	system("pause");
	return 0;
}

/*
测试数据：
4 5
0123
0 1 2
1 2 4
2 3 3
1 3 1
0 3 2
*/
/*
输入总节点数和总边数：6 6
输入各个节点的值：012345
输入一条边的两个节点以及边的权值：0 1 1
输入一条边的两个节点以及边的权值：1 2 2
输入一条边的两个节点以及边的权值：2 3 4
输入一条边的两个节点以及边的权值：4 1 2
输入一条边的两个节点以及边的权值：4 5 4
输入一条边的两个节点以及边的权值：5 1 3
*/

运行结果

生活很美好，加油！！
记得点赞哦！！