《c语言求解多段图(向前处理法)》由会员分享，可在线阅读，更多相关《c语言求解多段图(向前处理法)（3页珍藏版）》请在金锄头文库上搜索。
1、#include#include#define Infinity 1000 /无穷大#define Max 45#define null 0typedef struct ArcNode /边结点int adjvex; /边的终点int weigh; /边的权struct ArcNode *nextarc; /下一条邻接边ArcNode;typedef struct VNode /顶结点char data; /顶点ArcNode *firstarc; /第一条邻接边VNode,AdjListMax;typedef struct /图int vexnum,arcnum; /顶点数，边数AdjLis
2、t vertices; /顶点集合表Graph;void CreatGraph(Graph *G) /建立有向图int i,j;FILE *fp;ArcNode *p;if(fp=fopen(Init.dat,r)=NULL) printf(Cannot open the file!n);exit(0);fscanf(fp,%d %d,&G-vexnum,&G-arcnum); /从文件中读取顶点数和边数for(i=1;ivexnum;i+) fscanf(fp,%c,&G-verticesi.data); /从文件中读取顶点名称G-verticesi.firstarc=NULL; /将第一条
3、邻接边的地址赋为空for(i=1;iadjvex,&p-weigh); p-nextarc=G-verticesj.firstarc; /使用插表头的方法插入邻接边G-verticesj.firstarc=p;void main()int i,j;int cost13,d13,q6;int b,min;Graph *G;G=(Graph*)malloc(sizeof(Graph);ArcNode *p;CreatGraph(G);printf(The Graph:n); /输出有向图for(i=1;ivexnum;i+) p=G-verticesi.firstarc;printf(%d%d,i
4、,p-adjvex);while(p-nextarc!=null)printf( %d,p-nextarc-adjvex);p=p-nextarc;printf(n);printf(12n);/向后处理法cost12=0;for(j=11;j=1;j-)p=G-verticesj.firstarc;min=p-weigh+costp-adjvex;costj=min;dj=p-adjvex;while (p-nextarc!=null)b=p-nextarc-weigh+costp-nextarc-adjvex;if(bnextarc-adjvex;p=p-nextarc;/找一条最小路径q1=1;q5=12;for(j=2;j,qi);printf(%d,qi);
