#include<iostream>
using namespace std;
typedef int elemtype;
const int n=9;//顶点数
const int e=11;//弧数目
class link
{
public:
elemtype data;
link *next;
int w;
};
class node
{
public:
int ve[n+1],v1[n+1];
int s1[100],s2[100];
int top1,top2;
link a[n+1];
void creatlink(node &g);
void topsort(node &g);
void critical_path(node &g);
};
void node::creatlink(node &g)
{
int i,j,k,w;
link *s;
for(i=1;i<=n;i++)//建立邻接表头结点
{
g.a[i].data=0;
g.a[i].next=NULL;
g.a[i].w=0;
}
cout<<"请输入一条边及权值:\n";
for(k=1;k<=e;k++)
{
cin>>i>>j>>w;//输入一条边
s=new link;
s->data=j;s->w=w;
s->next=g.a[i].next;
g.a[i].next=s;
g.a[j].data++;
}
}
void node::topsort(node &g)
{
int j,k,m=0;
link *p;
top1=0;top2=0;
for(int x=1;x<=n;x++)ve[x]=0;
for(int i=1;i<=n;i++)
if(g.a[i].data==0)
{
top1++;s1[top1]=i;
}
while(top1>0)
{
int j;
j=s1[top1--];
s2[++top2]=j;m++;
p=g.a[j].next;
while(p!=NULL)
{
k=p->data;
g.a[k].data--;
if(g.a[k].data==0)s1[++top1]=k;
if(ve[j]+p->w>ve[k])ve[k]=ve[j]+p->w;
p=p->next;
}
}
}
void node::critical_path(node &g)
{
int j,k,kk,ee,e1;
link *p;
for(int y=1;y<=n;y++)v1[y]=ve[n];
while(top2>0)
{
j=s2[top2--];p=g.a[j].next;
while(p!=NULL)
{
k=p->data;kk=p->w;
if(v1[k]-kk<v1[j])v1[j]=v1[k]-kk;
p=p->next;
}
}
cout<<"关键路径为:\n";
for(j=1;j<=n;j++)
{
p=g.a[j].next;
while(p!=NULL)
{
k=p->data;kk=p->w;
ee=ve[j];e1=v1[k]-kk;
if(ee==e1)
cout<<"顶点"<<j<<"到顶点"<<k<<" ";
p=p->next;
}
}
cout<<endl;
}
int main()
{
node g;
g.creatlink(g);
g.topsort(g);
g.critical_path(g);
getchar();
getchar();
}
guanjianlujing.rar_关键路径
版权申诉
156 浏览量
2022-09-23
10:09:58
上传
评论
收藏 921B RAR 举报
寒泊
- 粉丝: 75
- 资源: 1万+