求教各位大侠们。。。这个错在哪哈？非常急。。。。。谢谢哦！
题目：v1->v2的权值是3
v2->v4的权值是2
v2->v5的权值是3
v3->v6的权值是3
v3->v4的权值是4
v4->v6的权值是2
v5->v6的权值是1
求该图的关键路径。
该程序运行结果的关键路径为什么只有v3 v4 v6 而没有v1 啊？？？
#define MVNum 100
#include <stdio.h>
#include<malloc.h>
#include <stdlib.h>
typedef struct node{/*边表结点类型*/
int adjvex;/*顶点序号*/
int dut;/*边上的权值*/
struct node *next;/*指向下一条边的指针*/
}EdgeNode;
typedef struct vnode{/*顶点表结点*/
int vertex;/*顶点域*/
int id;/*顶点入度*/
EdgeNode *link;/*边表头指针*/
}VNode,Adjlist[MVNum]; /*邻接表*/
typedef Adjlist AOELGraph;
void CreateGraph(AOELGraph GL,int n,int e){/*建立有向图存储结构，也就是建表。n为顶点数，e为边数*/
int i,j,k,l;
EdgeNode *p;
printf("please write into vertex of information and indegree\n:");
for(i=1;i<=n;i++){/*建立顶点表*/
scanf("%d,%d",&GL[i].vertex,&GL[i].id);
GL[i].link=NULL;/*边表头指针置为空*/
}
printf("***********+_+***********");
printf("please putinto edge <Vi,Vj> of i,j and edge of weight :\n");
for(k=1;k<=e;k++){/*采用头插法建立每一个顶点的邻接表*/
scanf("%d,%d,%d",&i,&j,&l);
p=(EdgeNode *)malloc(sizeof(EdgeNode));/*生成新的边表结点*/
p->adjvex=j;/*将邻接点序号j赋给新的结点的邻接点域*/
p->dut=l;
p->next=GL[i].link;
GL[i].link=p;/*将新的结点插入到顶点vi的边表头部*/
}
}
void CriticalPath(AOELGraph dig,int n){/*求关键路径,dig为AOE网带权邻接表*/
int i,j,k,m,front,rear;
int ve[MVNum],vl[MVNum],e[MVNum],l[MVNum];
int tpord[MVNum];
EdgeNode * p;
for(i=1;i<=n;i++)
ve[i]=0;/*将各事件的最早发生时间均置初始值为0*/
front=0 ;rear=0;/*初始化顺序队列的首尾指针*/
for(i=1;i<=n;i++){/*扫描顶点表，将入度为0的顶点入队*/
if(dig[i].id==0){
rear++;
tpord[rear]=i;
}
}
m=0;/*计数器初始化*/
while(front!=rear){
front++; j=tpord[front];/*Vi出队即删去Vi*/
m++;
p=dig[j].link;/*p为指向Vj的出边表的结点*/
while(p!=NULL){/*删去所有以Vj为起点的出边<vj,vk>*/
k=p->adjvex;/*k是边<vj,vk>中终点vk的序号*/
dig[k].id=dig[k].id-1;/*将vk入度减1*/
if((ve[j]+p->dut)> ve[k])
ve[k]=ve[j]+p->dut;/*修改ve(k)的值*/
if(dig[k].id==0){/*新的入度为0的顶点vk入队*/
rear++;
tpord[rear]=k;
}
p=p->next;/*找vj下一条出边*/
}/*while*/
}/*while*/
if(m<n){/*图中有回路，+_+退出算法！*/
printf("AOE net has reback road!\n");
return;
}
for(i=1;i<=n;i++)
vl[i]=ve[i];/*为各事件Vi的最迟发生时间vl(i)置初值*/
for(i=n-1;i>=1;i--){/*按拓扑排序的逆序取顶点vi*/
j=tpord[i];
p=dig[j].link;/*取vj出边表上第一个表结点*/
while(p!=NULL){
k=p->adjvex;/*k是边<vj,vk>的终点vk的序号*/
if((vl[k]-p->dut)> vl[j])
vl[j]=vl[k]-p->dut;/*修改 vl(j)的值，vl(j)=max {vl(j),vl(k)-dut(<j,k>)}*/
p=p->next;/*找vj下一条出边*/
}
}
i=0;/*边计数器初始化*/
for(j=1;j<=n;j++){/*扫描顶点表，依次取顶点vj*/
p=dig[j].link;
while(p!=NULL){/*扫描顶点vj的出边表，计算各边<vj,vk>所代表的活动ai的e(i)和l(i)*/
k=p->adjvex;i++;
e[i]=ve[j];
l[i]=vl[k]-p->dut;
printf("**********AIAI***********");
printf("vertex V%d To vertex V%d\n",dig[j].vertex,dig[k].vertex);
if(l[i]==e[i])
printf("Yes,it's key way!\n");
else
printf("No,it's no key way!\n");
p=p->next;
}/*while*/
}/*for*/
}
void main(){
int n,e;
AOELGraph GL;/*定义AOE网*/
printf("please putinto vertexnum 'n' and edge 'e': ");
scanf("%d,%d",&n,&e);
CreateGraph(GL,n,e);
CriticalPath(GL,n);
}
