关于图的关键路径

嘴角上扬

我写了一个计算图的关键路径的程序，可是出来的最早和最晚老是一样的，关键活动也不对，高手帮忙看看那里错了

1. #include "iostream.h"
   
2. #include "stdlib.h"
   
3. #include "malloc.h"
   
4. #define MAX 30
   
5. 
   
6. typedef struct node
   
7. {
   
8.         int vex;
   
9.         struct node *next;
   
10. }edgenode;
    
11. 
    
12. typedef struct vnode
    
13. {
    
14.         int id;
    
15.         struct node *link;
    
16. }vexnode;
    
17. 
    
18. typedef struct nodel
    
19. {
    
20.         int adgvex;
    
21.         int dut;
    
22.         struct nodel *next;
    
23. }edgenodel;
    
24. 
    
25. typedef struct vnodel
    
26. {
    
27.         int vertex;
    
28.         int id;
    
29.         struct nodel *link;
    
30. }vexnodel;
    
31. 
    
32. int na;
    
33. int creatAOE(vexnodel dig[]);
    
34. int creatAOV(vexnode dig[]);
    
35. void toposort(vexnode dig[],int n);
    
36. void criticalpath(vexnodel dig[],int n);
    
37. 
    
38. void main()
    
39. {
    
40.         vexnodel dig[MAX];
    
41.         vexnode dig2[MAX];
    
42.         int n=0;
    
43.         int cord=1;
    
44.         while (1)
    
45.         {
    
46.                 cout<<"     主菜单     "<<endl;
    
47.                 cout<<"1.建立AOV邻接链表"<<endl;
    
48.                 cout<<"2.建立AOE邻接链表"<<endl;
    
49.                 cout<<"3.拓扑排序"<<endl;
    
50.                 cout<<"4.求关键路径"<<endl;
    
51.                 cout<<"输入代码选择：（1-4），0表示结束"<<endl;
    
52.                 cin>>cord;
    
53.                 switch(cord)
    
54.                 {
    
55.                 case 1:
    
56.                         n=creatAOV(dig2);
    
57.                         break;
    
58.                 case 2:       
    
59.                         cout<<"input Arcs:";
    
60.                         cin>>na;
    
61.                         n=creatAOE(dig);
    
62.                         break;
    
63.                 case 3:
    
64.                         toposort(dig2,n);
    
65.                         break;
    
66.                 case 4:
    
67.                         criticalpath(dig,n);
    
68.                         break;
    
69.                 case 0:
    
70.                         exit(9);
    
71.                 }
    
72.         }
    
73. }
    
74. 
    
75. int creatAOE(vexnodel dig[])
    
76. {
    
77.         int vextotal,j,a,b,c;
    
78.         edgenodel *p;
    
79.         cout<<"input vex number:";
    
80.         cin>>vextotal;
    
81.         for(j=0;j<MAX;j++)
    
82.         {
    
83.                 dig[j].vertex=j;
    
84.                 dig[j].id=0;
    
85.                 dig[j].link=NULL;
    
86.         }
    
87.         for(j=1;j<=na;j++)
    
88.         {
    
89.                 cout<<"input edge<i,j>weight:";
    
90.                 cin>>a>>b>>c;
    
91.                 dig[b].id++;
    
92.                 p=(edgenodel*)malloc(sizeof(edgenodel));
    
93.                 p->adgvex=b;
    
94.                 p->dut=c;
    
95.                 p->next=dig[a].link;
    
96.                 dig[a].link=p;
    
97.         }
    
98.         cout<<"output link table"<<endl;
    
99.         for(j=1;j<=vextotal;j++)
    
100.         {
     
101.                 cout<<j<<"   "<<dig[j].id<<"   ";
     
102.                 p=dig[j].link;
     
103.                 while (p!=0)
     
104.                 {
     
105.                         cout<<p->adgvex<<"   "<<p->dut<<"   ";
     
106.                         p=p->next;
     
107.                 }
     
108.                 cout<<endl;
     
109.         }
     
110.         return(vextotal);
     
111. }
     
112. 
     
113. int creatAOV(vexnode dig[])
     
114. {
     
115.         int vextotal,arcnumber,j,a,b;
     
116.         edgenode *p;
     
117.         cout<<" input vex number:";
     
118.         cin>>vextotal;
     
119.         cout<<" input Arc number:";
     
120.         cin>>arcnumber;
     
121.         for(j=0;j<MAX;j++)
     
122.         {
     
123.                 dig[j].id=0;
     
124.                 dig[j].link=NULL;
     
125.         }
     
126.         for(j=1;j<=arcnumber;j++)
     
127.         {
     
128.                 cout<<" input vex number<i,j>:"<<endl;
     
129.                 cin>>a>>b;
     
130.                 dig[b].id++;
     
131.                 p=(edgenode*)malloc(sizeof(edgenode));
     
132.                 p->vex=b;
     
133.                 p->next=dig[a].link;
     
134.                 dig[a].link=p;
     
135.         }
     
136.         cout<<" output link table"<<endl;
     
137.         for(j=1;j<=vextotal;j++)
     
138.         {
     
139.                 cout<<j<<"   "<<dig[j].id<<"   ";
     
140.                 p=dig[j].link;
     
141.                 while (p!=NULL)
     
142.                 {
     
143.                         cout<<p->vex<<"   ";
     
144.                         p=p->next;
     
145.                 }
     
146.                 cout<<endl;
     
147.         }
     
148.         return(vextotal);
     
149. }
     
150. 
     
151. void toposort(vexnode dig[],int n)
     
152. {
     
153.         edgenode *p;
     
154.         int i,j,k,top,m;
     
155.         top=0;
     
156.         m=0;
     
157.         for(i=0;i<n;i++)
     
158.         {
     
159.                 if (dig[i].id==0)
     
160.                 {
     
161.                         dig[i].id=top;
     
162.                         top=i;
     
163.                 }
     
164.         }
     
165.         while (top>0)
     
166.         {
     
167.                 j=top;
     
168.                 top=dig[top].id;
     
169.                 cout<<j;
     
170.                 m++;
     
171.                 p=dig[j].link;
     
172.                 while (p!=NULL)
     
173.                 {
     
174.                         k=p->vex;
     
175.                         dig[k].id--;
     
176.                         if (dig[k].id==0)
     
177.                         {
     
178.                                 dig[k].id=top;
     
179.                                 top=k;
     
180.                         }
     
181.                         p=p->next;
     
182.                         }
     
183.                 cout<<"  ";
     
184.         }
     
185.         if (m<n)
     
186.                 cout<<" The network has acycle."<<endl;
     
187. }
     
188. 
     
189. void criticalpath(vexnodel dig[],int n)
     
190. {
     
191.         int front=0,rear=0;
     
192.         int tpord[20],vl[20],ve[20];
     
193.         int l[20],e[20],i,j,k,m;
     
194.         edgenodel *p;
     
195.         for(i=1;i<=n;i++) ve[i]=0;
     
196.         for(i=1;i<=n;i++)
     
197.                 if(dig[i].id==0) tpord[++rear]=i;
     
198.         m=0;
     
199.         while (front!=rear)
     
200.         {
     
201.                 front++;
     
202.                 j=tpord[front];
     
203.                 m++;
     
204.                 p=dig[j].link;
     
205.                 while (p)
     
206.                 {
     
207.                         k=p->adgvex;
     
208.                         dig[k].id--;
     
209.                         if(dig[k].id==0) tpord[++rear]=k;
     
210.                         if(ve[j]+p->dut>ve[k]) ve[k]=ve[j]+p->dut;
     
211.                         p=p->next;
     
212.                 }
     
213.         }
     
214.         if (m<n) cout<<" The AOE network has acycle"<<endl;
     
215.         for(i=1;i<=n;i++) vl[i]=ve[i];
     
216.         for(i=n;i>0;i--)
     
217.         {
     
218.                 j=tpord[i];
     
219.                 p=dig[j].link;
     
220.                 while (p)
     
221.                 {
     
222.                         k=p->adgvex;
     
223.                         if ((vl[k]-p->dut)<vl[j]) vl[j]=vl[k]-p->dut;
     
224.                         p=p->next;
     
225.                 }
     
226.         }
     
227.         cout<<" output VE VL"<<endl;
     
228.         for(i=1;i<=n;i++)
     
229.                 cout<<ve[i]<<"   "<<vl[i]<<endl;
     
230.         for(j=1,i=1;j<=n;j++,i++)
     
231.         {
     
232.                 p=dig[j].link;
     
233.                 while (p)
     
234.                 {
     
235.                         k=p->adgvex;
     
236.                         e[i]=ve[j];
     
237.                         l[i]=vl[k]-p->dut;
     
238.                         cout<<dig[j].vertex<<"   "<<dig[k].vertex<<"   "<<e[i]<<"   "<<l[i]<<"   "<<l[i]-e[i];
     
239.                         if (l[i]==e[i])
     
240.                                 cout<<"        CRITICAL ACTIVITY"<<endl;
     
241.                         else
     
242.                                 cout<<endl;
     
243.                         p=p->next;
     
244.                 }
     
245.         }
     
246. }

复制代码

                               
登录/注册后可看大图

该贴已经同步到 嘴角上扬的微博