实验名称：最短路径和关键路径的研究与实现     

班级            姓名        学号            实验日期：            

实验机时：2 学时                         实验成绩：

-------------------------------------------------------------------------------

一.实验目的：

掌握图的邻接矩阵、邻接表的表示方法

掌握迪杰斯特拉和弗洛伊德的最短路径算法

理解拓扑排序，掌握关键路径的算法

二.加深对图的理解，逐步培养解决实际问题的编程能力实验内容：

（1）基本实验内容：

最短路径和关键路径的实现

三.程序及注释：

#include"stdio.h"

#include"stdlib.h"

#define VEX_NUM 10//定义最大顶点数

#define ARC_NUM 20//定义最多边数

typedef int vertype;

struct arcnode//声明边表中结点结构

{int adjvex;

int dut;   //边上的权值

struct arcnode *nextarc;};

struct node      //声明头结点结构

{int data;

int id;      //定点入度

struct arcnode *firstarc;};

typedef struct node ALgraph[VEX_NUM+1];

void create_ALgraph(ALgraph g,int e,int n)

{  //建立AOE网的邻接表，e为弧的数目，n为顶点数

struct arcnode *p;

int i,j,k,w;

printf("请输入顶点的信息和入度，用空格间隔:");

for(i=1;i<=n;i++) //结点下标从1开始

{scanf("%d%d",&g[i].data,&g[i].id);  //输入顶点信息和入度

g[i].firstarc=NULL;}

for(k=1;k<=e;k++) //建立边表

{printf("请输入边的两个顶点以及边上的权值，用空格间隔:");

scanf("%d%d%d",&i,&j,&w);  //输入有向边的两个顶点

p=(struct arcnode *)malloc(sizeof(struct arcnode));

p->adjvex=j;

p->dut=w;

p->nextarc=g[i].firstarc; //插入下标为i的边表的第一个结点的位置

g[i].firstarc=p;}}

void oupe_ALgraph(ALgraph g,int n)   //输出AOE网的邻接表

{int i;

struct arcnode *p;

for(i=1;i{p=g[i].firstarc;

printf("%d,%d->",g[i].data,g[i].id);

while(p!=NULL)

{printf("%3d%3d",p->adjvex,p->dut);

p=p->nextarc; //找下一个邻接点

}

printf("\\n");}}

int Criticalpath(ALgraph g,int n)//求AOE网的各个关键活动

{int i,j,k,count;

int tpord[VEX_NUM+1];   //顺序队列

int ve[VEX_NUM+1],le[VEX_NUM+1];

int e[ARC_NUM+1],l[ARC_NUM+1];

int front=0,rear=0;//顺序队列的首尾指针初值为0

struct arcnode *p;

for(i=1;i<=n;i++) //各事件最早发生事件初值为0

ve[i]=0;

for(i=1;i<=n;i++)

if(g[i].id==0)   //入度为0入队列

tpord[++rear]=i;

count=0;

while(front!=rear)

{front++;

j=tpord[front];

count++;

p=g[j].firstarc;

while(p!=NULL)

{k=p->adjvex;

g[k].id--;

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

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

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

tpord[++rear]=k;

p=p->nextarc;}}

if(countreturn 0;

for(i=1;i<=n;i++) //各事件的最迟发生事件赋初值

le[i]=ve[n];

for(i=n-1;i>=1;i--) //按拓扑序列的逆序取顶点

{j=tpord[i];

p=g[j].firstarc;

while(p!=NULL)

{k=p->adjvex;

if(le[k]-p->dutle[j]=le[k]-p->dut;

p=p->nextarc;}}

i=0;

for(j=1;j<=n;j++)

{p=g[j].firstarc;

while(p!=NULL)    //计算各边所代表的a(i+1)的e[i]和l[i]         

{k=p->adjvex;

e[i]=ve[j];

l[i]=le[k]-p->dut;

if(l[i]==e[i])  //输出关键活动

printf(":%d\\n",g[j].data,g[k].data,p->dut);

p=p->nextarc;

i++;}}

return 1;}

main()

{ALgraph g;

int e,n;

int tag;

printf("\\n请输入顶点的个数和边的个数，用空格间隔:");

scanf("%d%d",&n,&e);

create_ALgraph(g,e,n);     //建立邻接表

printf("\\n输出邻接表信息:\\n");

oupe_ALgraph(g,n);    //建立输出邻接表

printf("\\n输出AOE网的关键路径:\\n");

printf("弧:权值\\n");

tag=Criticalpath(g,n);     /关键活动

if(!tag)

printf("AOE网有回路\\n");｝

四.运行结果：

五.实验心得：

数据结构是计算机程序设计的重要理论技术基础。这次课程设计运用C语言作为数据结构和算法的描述语言对数据的存储结构和算法进行描述。这次任务提高了我们对实际问题的解决能力，即运用所学的知识对问题进行分析：了解问题的基本要求，怎样将实际问题转化成学科语言的输入输出，要用到什么知识来存储信息。 

虽然这次的课程设计有点困难，在网上借鉴了部分代码的情况下做的还是不够完美，有很多的基本算法思想还不是很理解，但是我没有放弃，让我学会怎样在遇到困难的时候去解决问题，去坚持。同时也让我感受到了数据结构的乐趣，坚定了我学习数据结构的决心。下载本文