c语言求解多段图(向前处理法).docx

《c语言求解多段图(向前处理法).docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include#include#defineInfinity1000//无穷大#defineMax45#definenull0typedefstructArcNode//边结点{intadjvex;//边的终点intweigh;//边的权structArcNode*nextarc;//下一条邻接边}ArcNode;typedefstructVNode//顶结点{chardata;//顶点ArcNode*firstarc;//第一条邻接边}VNode,AdjList[Max];typedefstruct//图{intvexnum,arcnum;//顶点数，

2、边数AdjListvertices;//顶点集合表}Graph;voidCreatGraph(Graph*G)//建立有向图{inti,j;FILE*fp;ArcNode*p;if((fp=fopen("Init.dat","r"))==NULL){printf("Cannotopenthefile!");exit(0);}fscanf(fp,"%d%d",&G->vexnum,&G->arcnum);//从文件中读取顶点数和边数for(i=1;i<=G->vexnum;i++){fscanf(fp,"%c",&G->vertices[i].data);//从文件中读取顶点名称G->ver

3、tices[i].firstarc=NULL;//将第一条邻接边的地址赋为空}for(i=1;i<=(*G).arcnum;i++){p=(ArcNode*)malloc(sizeof(ArcNode));fscanf(fp,"%d%d%d",&j,&p->adjvex,&p->weigh);p->nextarc=G->vertices[j].firstarc;//使用插表头的方法插入邻接边G->vertices[j].firstarc=p;}}voidmain(){inti,j;intcost[13],d[13],q[6];intb,min;Graph*G;G=(Graph*)malloc(

4、sizeof(Graph));ArcNode*p;CreatGraph(G);printf("TheGraph:");//输出有向图for(i=1;ivexnum;i++){p=G->vertices[i].firstarc;printf("%d-->%d",i,p->adjvex);while(p->nextarc!=null){printf("%d",p->nextarc->adjvex);p=p->nextarc;}printf("");}printf("12");//向后处理法cost[12]=0;for(j=11;j>=1;j--){p=G->vertices[j

5、].firstarc;min=p->weigh+cost[p->adjvex];cost[j]=min;d[j]=p->adjvex;while(p->nextarc!=null){b=p->nextarc->weigh+cost[p->nextarc->adjvex];if(bnextarc->adjvex;}p=p->nextarc;}}//找一条最小路径q[1]=1;q[5]=12;for(j=2;j<=4;j++)q[j]=d[q[j-1]];printf("ashortestwayis:");for(i=1;i<=4

6、;i++)printf("%d-->",q[i]);printf("%d",q[i]);}