向前和向后处理多段图的算法设计和实现

《向前和向后处理多段图的算法设计和实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、//多段图问题的动态规划算法设计与实现#include"stdio.h"#include"conio.h"#include"stdlib.h"#definen12/*图的顶点数*/#definek5/*图的段数*/#defineMAX1000typedefintNodeNumber;/*节点编号*/typedefintCostType;/*成本值类型*/CostTypecost[n][n];NodeNumberpath[k];/*存储最短路径的数组*/NodeNumbercur=-1;voidcreatgraph(CostTypecost[n][n])/*创建

2、图的成本矩阵*/{inti,j;printf("请输入图的成本矩阵:");for(i=0;i

3、ost[n][n],NodeNumberpath[k]){inti,j,length,temp,v[n],d[n];for(i=0;i=0;i--){for(length=MAX,j=i+1;j<=n-1;j++)if(cost[i][j]>0&&(cost[i][j])+v[j]

4、d[path[i-1]];printf("请输出选择V[i]:");for(i=0;i

5、CostTypecost[n][n],NodeNumberpath[k]){inti,j,length,temp,v[n],d[n];for(i=0;i=0;j--)if(cost[j][i]>0&&(cost[j][i])+v[j]

6、i>=1;i--)(path[i])=d[path[i+1]];printf("请输出选择V[i]:");for(i=n-1;i>0;i--)printf("%3d",v[i]);printf("------------------------------------------");printf("请输出决策D[i]:");for(i=n-1;i>0;i--)printf("%3d",d[i]);printf("------------------------------------------");}/*查找结点i的后向邻接

7、结点*/intfindbackward(CostTypecost[n][n],NodeNumberi,NodeNumbercur){intj;for(j=cur+1;j0){cur=j;returnj;}return-1;}/*查找结点i的前向邻接结点*/intfindforward(CostTypecost[n][n],NodeNumberi,NodeNumbercur){intj;for(j=cur+1;j0){cur=j;returnj;}return-1;}/*输出最短

8、路径序列*/voidoutpath(N