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

动态规划找出多段图的最小花费通路算法（C语言）/算法：#include #include #define MAX 50#define MAX_LEN 100 /*定义顶点之间最大花费（假设最大花费为100）*/结构体定义typedef struct edgenode /*定义边表结点结构体*/int adjvertex; /*邻接点编号*/int len; /*该结点与父结点之间的花费*/struct edgenode *next; /*指向下一个邻接点*/ EdgeNode;typedef struct vertexnode /*定义顶点结点结构体*/EdgeNode *firstedge; /*边表头指针*/ VertexNode;typedef struct /*定义邻接表结构体*/VertexNode adjlistMAX; /*邻接表*/int vertexNum; /*顶点数*/int edgeNum; /*边数*/ ALGraph;/函数声明ALGraph * CreateALGraph(int vertexNum, int edgeNum);void MultistageGraph(ALGraph *G, int n, int route, int *minCost);/主函数int main()ALGraph *G = NULL;int vertexNum, edgeNum; /*顶点数和边数*/int *route; /*从源点到收点的最短路径上的顶点编号*/int minCost; /*最短路径的最小费用*/int i;printf(请输入顶点数和边数：n);scanf(%d,%d, &vertexNum,&edgeNum);/初始化GG = CreateALGraph(vertexNum, edgeNum);if(!G)return 0;/初始化route数组route = (int *)malloc(sizeof(int) * vertexNum);MultistageGraph(G, vertexNum, route, &minCost);/输出最小花费路径及最小花费printf(n最小花费路径是：n);for(i = 0; i , routei);if(routei = (vertexNum - 1)printf(bbbb n);break;printf(n最小花费是：%dn, minCost);return 0;/*函数名称：GreateALGraph函数功能：初始化有向图的邻接表输入：顶点数ertexNum，边数edgeNum输出：指向已初始化完毕的有向图的邻接表指针*/ALGraph * CreateALGraph(int vertexNum, int edgeNum)ALGraph *G = NULL;int i, j, u, v, info;G = (ALGraph *)malloc(sizeof(ALGraph);if(G)G-vertexNum = vertexNum;G-edgeNum = edgeNum;for(i = 0; i adjlisti.firstedge = NULL;/给边表结点分配内存空间printf(请输入分段图中各相邻结点的编号及其权值：n);for(j = 0; j next = NULL;/输入相邻结点的编号及其边上的权值scanf(%d,%d,%d, &u, &v, &info);if(pnode)pnode-next = G-adjlistu.firstedge;G-adjlistu.firstedge = pnode;pnode-adjvertex = v;pnode-len = info;elsereturn NULL;return G;/*函数名称：MultistageGraph函数功能：多段图中利用动态规划找出源点到收点的最小花费通路输入：指向有向图的邻接表指针G，结点个数n，保存最小花费通路结点的数组route，保存最小花费minCost输出：最小花费通路结点的数组route，最小花费minCost*/void MultistageGraph(ALGraph *G, int n, int route, int *minCost)int *cost; /*每个结点到收点的最小费用*/int *path; /*在阶段决策中，各个顶点到收点的最短路径上的前方顶点编号*/int i;/给cost、path、route指针分配n个int大小的内存空间cost = (int *)malloc(sizeof(int) * n);path = (int *)malloc(sizeof(int) * n);/初始化cost、path、route指向的内存空间for(i = 0; i = 0; i -) EdgeNode *pnode = G-adjlisti.firstedge;while(pnode & (pnode-len + costpnode-adjvertex) len + costpnode-adjvertex;pathi = pnode-adjvertex;pnode = pnode-next; i = 0;while(routei != n-1)