最短路径c语言代码.txt

关于最短路径的算法

#include<stdio.h>

#include<stdlib.h>

#include<iomanip.h>

#include <process.h>

//#define PROJECTNUMBER 9//10

//#define PLANNUMBER 11//13

typedef struct node

{

	int adjvex;//邻接顶点

	int dut;

	struct node *next;

}edgenode;//边缘结点

typedef struct 

{

	int projectname;

	int id;

	edgenode *link;

}vexnode;//链表

//vexnode Graphicmap[PROJECTNUMBER];

void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)//生成图

{

	int begin,end,duttem;

	edgenode *p;

	for(int i=0;i<projectnumber;i++)

	{

		Graphicmap.projectname=i;

		Graphicmap.id =0;

		Graphicmap.link =NULL;

	} 

	printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n");

	printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n");

	for(int k=0;k<activenumber;k++)

	{

		scanf("%d,%d,%d",&begin,&end,&duttem);

		p=(edgenode*)malloc(sizeof(edgenode));

		p->adjvex =end-1;

		p->dut =duttem;

		Graphicmap[end-1].id ++;
	
		p->next =Graphicmap[begin-1].link ;
	
		Graphicmap[begin-1].link =p;//插入结点

	}

}

int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime)

{

	int i,j,k,m=0;

	int front=-1,rear=-1;

	int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列

	int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间

	int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间

	int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间

	int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间

	edgenode *p;

	totaltime=0;

	for(i=0;i<projectnumber;i++) ve=0;

	for(i=0;i<projectnumber;i++)

	{

		if(Graphicmap.id==0)

	{

		topologystack[++rear]=i;

		m++;

	}

}

while(front!=rear)

{

	front++;

	j=topologystack[front];

	m++;

	p=Graphicmap[j].link ;

	while(p)

	{

		k=p->adjvex ;

		Graphicmap[k].id --;

		if(ve[j]+p->dut >ve[k])

		ve[k]=ve[j]+p->dut ;

		if(Graphicmap[k].id ==0)

			topologystack[++rear]=k;

		p=p->next ;

	}

}

if(m<projectnumber)

{

	printf("\n本程序所建立的图有回路不可计算出关键路径\n");

	printf("将退出本程序\n");

	return 0;

}

totaltime=ve[projectnumber-1];

for(i=0;i<projectnumber;i++)

	vl=totaltime;

for(i=projectnumber-2;i>=0;i--)

{

	j=topologystack;

	p=Graphicmap[j].link ;

	while(p)

	{

		k=p->adjvex ;

		if((vl[k]-p->dut )<vl[j])

			vl[j]=vl[k]-p->dut ;

		p=p->next ;

	}

}

i=0;

printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |\n");

for(j=0;j<projectnumber;j++)

{

	p=Graphicmap[j].link;

while(p)

{

	k=p->adjvex ;

	e[++i]=ve[j];

	l=vl[k]-p->dut;

	printf("| %4d | %4d | %4d | %4d | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e,l,l-e);

	if(l==e)

		printf(" 关键活动 |");

	printf("\n");

	p=p->next ;

}

}

return 1;

}

void seekkeyroot()

{

	int projectnumber,activenumber,totaltime=0;

	system("cls");

	printf("请输入这个工程的化成图形的节点数:");

	scanf("%d",&projectnumber);

	printf("请输入这个工程的活动个数:");

	scanf("%d",&activenumber);

	vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));

	CreateGraphic(Graphicmap,projectnumber,activenumber);

	SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);

	printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime);

	system("pause");

}

int main()

{



	char ch;

	for(;;)

	{

	do 

	{

		system("cls");

		printf("| 欢迎进入求关键路径算法程序 |");

		for(int i=0;i<80;i++)printf("*");

		printf("%s","(S)tart开始输入工程的节点数据并求出关键路径\n");

		printf("%s","(E)xit退出\n");

		printf("%s","请输入选择:");

		scanf("%c",&ch);

		ch=toupper(ch);

	}while(ch!='S'&&ch!='E');

	switch(ch)

	{

		case'S':

		seekkeyroot();

		break;

		case'E': 

		return 1;

	}

}

}


-----------------------------------------------------------------------------------------
设有一个工程网络如下图表示(无环路的有向图)：

　其中，顶点表示活动，①表示工程开始，⑤表示工程结束(可变，用N表示)，边上的数字表示活动延续
的时间。



如上图中，活动①开始5天后活动②才能开始工作，而活动③则要等①、②完成之后才能开始，即最早也
要7天后才能工作。

　在工程网络中，延续时间最长的路径称为关键路径。上图中的关键路径为：①—②—③—④—⑤共18天
完成。

　关键路径的算法如下：

1.数据结构：

　R[1..N，1..N]OF INTEGER；　　　表示活动的延续时间，若无连线，则用-1表示；

　EET[1..N]　　　　　　　　　　　表示活动最早可以开始的时间

　ET[1..N]　　　　　　　　　　 　表示活动最迟应该开始的时间

关键路径通过点J，具有如下的性质：EET[J]=ET[J]

2.约定：

　结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动。

程序清单：

PROGRAM GAO7_6；
　VAR I，J，N，MAX，MIN，W，X，Y：INTEGER；
　　　R：ARRAY[1..20，1..20]　OF INTEGER；
　　　EET，ET：ARRAY[1..20]　OF INTEGER；
　BEGIN
　　READLN(N)
　　FOR I:=1 TO N DO
　　　FOR J:=1 TO N DO 
　　　　R[I，J]:=-1；
　　READLN(X，Y，W)；{输入从活动X到活动Y的延续时间，以0为结束}
　WHILE X<>0 DO
　　　BEGIN
　　　　R[X，Y]:=W；　READLN(X，Y，W)
　　　END；
　　EET[1]：=0；{认为工程从0天开始}
　　FOR I：=2 TO N DO 
　　　BEGIN
　　　　MAX:=0；
　　　　FOR J:=1 TO N DO 
　　　　　IF R[J，I]<>-1 THEN
　　　　　　　IF　R[J，I]+EET[J]>MAX　THEN MAX:=R[J，I]+EET[J]；
　　　　EET[I]:=MAX；
　　　END；
　　　　 ET[N]：=EET[N]；
　　　FOR I：=N-1 DOWNTO 1 DO
　　　　BEGIN
　　　　　MIN：=10000；
　　　　　FOR J：=1 TO N DO 
　　　　　　IF R[I，J]<>-1 THEN
　　　　　　　　IF　　ET[J]-R[I，J]<MIN,
THEN MIN：=ET[J] - R[I，J]；
　　　　　　　ET[I]：=MIN；
　　　　　　END；
　　　　WRITELN(EET[N])；
　　　　FOR I：=1 TO N -1 DO 
　　　　　IF　EET[I]=ET[I]
　THEN WRITE(I，'→')；
　　WRITE(N)；READLN
END.