duo.c

给定一个多段图输入权值

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 50
typedef struct ArcNode{
	int adjvex;
	int value;
	struct ArcNode *nextarc;
}ArcNode,*node;
typedef struct VNode{
	int data;
    ArcNode *firstArc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct Graph{
	AdjList vertices;
	int vexnum,arcnum;
}*ALGraph;

int build_adList(ALGraph G,int n,int a){/*建立邻接表*/
  int v,m,i,t,h;
  node p,q;
  if(n<0) return printf("ERROR");
  G->vexnum=n;
  if(a<0) return printf("ERROR"); 
  G->arcnum=a;
  for(m=0;m<n;m++)
  {G->vertices[m].data=m; 
   G->vertices[m].firstArc=NULL;
  }
  for(m=1;m<=a;m++)
  {i=1;
   printf("输入第%d条弧:",m);
    scanf("%d,%d,%d",&t,&h,&v);
    p=(ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex=h;
	p->value=v;
	p->nextarc=NULL;
	while(G->vertices[i].data!=t){i++;}
   if(!G->vertices[i].firstArc) {
		G->vertices[i].firstArc=p;
  	}
   else
    {
      for(q=G->vertices[i].firstArc;q->nextarc;q=q->nextarc);
      q->nextarc=p;
   	}
  }
  return v;
}



void print_Graph(ALGraph G){/*打印邻接表*/
	ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));
	int i;
	for(i=1;i<G->vexnum;i++){
		p=G->vertices[i].firstArc;
		printf("[%d]",i);
		while(p){
			printf("->%d,%d",p->adjvex,p->value);
			p=p->nextarc;
		}printf("\n");
	}
}


fgraph(ALGraph G ,int k,int n){/*多段图ALGraph G，n 节点数，k图的段数
                                 输入是按段的顺序给节点编号*/
int cost[100];
int d[100];
int path[100];
int j,r,i,min,w,value;
node p;
cost[n]=0;
for( j=n-1;j>=1;j--){
    p=G->vertices[j].firstArc;
    min=p->value+cost[p->adjvex];
    r=p->adjvex;
	value=p->value;
	while(p!=NULL){/*r是一个的这样的结点，权值c(j,r)+cost[r]取最小值*/
    if((p->value+cost[p->adjvex])<min){
    min=p->value+cost[p->adjvex];
    r=p->adjvex;
	value=p->value;
	}
   	p=p->nextarc;
}
    
	
	cost[j]=value+cost[r];
    d[j]=r;
}
path[1]=1;path[k]=n;
for( i=2 ;i<=k-1;i++){/*找路径上的第j个节点*/
path[i]=d[path[i-1]];
}

printf("最小成本为:%d\n",cost[1]);
printf("最小成本路径为: ");
for(w=1;w<=k;w++){
printf("%d->",path[w]);
}
}

main(){
  	ALGraph g;  
    int n,a,k;
	g=(ALGraph)malloc(sizeof(ALGraph));
    printf("请输入多段图节点数目:");
    scanf("%d",&n);
	printf("请输入多段图边的数目:");
    scanf("%d",&a);
	printf("请输入多段图的段数:");
	scanf("%d",&k);
    printf("输入多段图的弧的信息（弧头，弧尾，权值）\n");
	build_adList(g,n,a);
    printf("多段图的邻接表为:\n");
	print_Graph(g);
    fgraph(g,k,n);

    getch();

}