动态规划-多段图-最小花费通路算法-C语言.doc

《动态规划-多段图-最小花费通路算法-C语言.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划找出多段图的最小花费通路算法（C语言）//算法：#include#include#defineMAX50#defineMAX_LEN100/*定义顶点之间最大花费（假设最大花费为100）*///结构体定义typedefstructedgenode{/*定义边表结点结构体*/intadjvertex;/*邻接点编号*/intlen;/*该结点与父结点之间的花费*/structedgenode*next;/*指向下一个邻接点*/}EdgeNode;typedefstructvertexnode{/*定义顶点结点结构体*/E

2、dgeNode*firstedge;/*边表头指针*/}VertexNode;typedefstruct{/*定义邻接表结构体*/VertexNodeadjlist[MAX];/*邻接表*/intvertexNum;/*顶点数*/intedgeNum;/*边数*/}ALGraph;//函数声明ALGraph*CreateALGraph(intvertexNum,intedgeNum);voidMultistageGraph(ALGraph*G,intn,introute[],int*minCost);//主函数intmain(){ALGraph*G=NULL;in

3、tvertexNum,edgeNum;/*顶点数和边数*/int*route;/*从源点到收点的最短路径上的顶点编号*/intminCost;/*最短路径的最小费用*/inti;printf("请输入顶点数和边数：");scanf("%d,%d",&vertexNum,&edgeNum);//初始化GG=CreateALGraph(vertexNum,edgeNum);if(!G){return0;}//初始化route数组route=(int*)malloc(sizeof(int)*vertexNum);MultistageGraph(G,vertexNum

4、,route,&minCost);//输出最小花费路径及最小花费printf("最小花费路径是：");for(i=0;i",route[i]);if(route[i]==(vertexNum-1)){printf("bbbb");break;}}printf("最小花费是：%d",minCost);return0;}/***********************************************************函数名称：GreateALGraph函数功能：初

5、始化有向图的邻接表输入：顶点数ertexNum，边数edgeNum输出：指向已初始化完毕的有向图的邻接表指针***********************************************************/ALGraph*CreateALGraph(intvertexNum,intedgeNum){ALGraph*G=NULL;inti,j,u,v,info;G=(ALGraph*)malloc(sizeof(ALGraph));if(G){G->vertexNum=vertexNum;G->edgeNum=edgeNum;for(i=0;i

6、adjlist[i].firstedge=NULL;}//给边表结点分配内存空间printf("请输入分段图中各相邻结点的编号及其权值：");for(j=0;jnext=NULL;//输入相邻结点的编号及其边上的权值scanf("%d,%d,%d",&u,&v,&info);if(pnode){pnode->next=G->adjlist[u]

7、.firstedge;G->adjlist[u].firstedge=pnode;pnode->adjvertex=v;pnode->len=info;}else{returnNULL;}}}returnG;}/***********************************************************函数名称：MultistageGraph函数功能：多段图中利用动态规划找出源点到收点的最小花费通路输入：指向有向图的邻接表指针G，结点个数n，保存最小花费通路结点的数组route，保存最小花费minCost输出：最小花费通路结点的数组rou

8、te，最小