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

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

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、(CostTypecost[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、;i++)(path[i])=d[path[i-1]];printf("请输出选择V[i]:");for(i=0;i

5、多段图的最短路径*/voidBPath(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、;path[k-1]=n-1;for(i=k-2;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("------------------------------

7、------------");}/*查找结点i的后向邻接结点*/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;j

8、>0){cur=j;returnj;}return-1;}/*输出最短路径序列*/voidoutpath(N