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

/多段图问题的动态规划算法设计与实现#include stdio.h#include conio.h #include stdlib.h#define n 12 /*图的顶点数*/#define k 5 /*图的段数*/#define MAX 1000typedef int NodeNumber; /*节点编号*/typedef int CostType; /*成本值类型*/CostType costnn;NodeNumber pathk; /*存储最短路径的数组*/NodeNumber cur= -1;void creatgraph(CostType costnn) /*创建图的成本矩阵*/int i,j;printf(请输入图的成本矩阵:n);for(i=0;in;i+)for(j=0;jn;j+) scanf(%d,&costij);void outgraph(CostType costnn) /*输出图的成本矩阵*/ int i,j;printf(输出图的成本矩阵:n); for(i=0;in;i+) for(j=0;jn;j+)printf(%3d,costij); printf(n);/* 使用向前递推算法求多段图的最短路径*/void FPath(CostType costnn,NodeNumber pathk)int i,j,length,temp,vn,dn;for(i=0;i=0;i-) for(length=MAX,j=i+1;j0 & (costij)+vjlength) length=costij+vj; temp=j;vi=length;di=temp;path0=0;pathk-1=n-1;for(i=1;i=k-2;i+) (pathi)=dpathi-1; printf(n请输出选择Vi:n); for(i=0;in-1;i+) printf(%3d,vi); printf(n-n); printf(n请输出决策Di:n); for(i=0;in-1;i+) printf(%3d,di); printf(n-n);/* 使用向后递推算法求多段图的最短路径*/void BPath(CostType costnn,NodeNumber pathk) int i,j,length,temp,vn,dn;for(i=0;in;i+) vi=0; /矩阵元素全部赋初值为for(i=1;i=0;j-)if(costji0 & (costji)+vj=1;i-) (pathi)=dpathi+1; printf(n请输出选择Vi:n); for(i=n-1;i0;i-) printf(%3d,vi); printf(n-n); printf(n请输出决策Di:n); for(i=n-1;i0;i-) printf(%3d,di); printf(n-n);/* 查找结点i的后向邻接结点*/int findbackward(CostType costnn,NodeNumber i,NodeNumber cur)int j; for(j=cur+1;j0) cur=j;return j;return -1;/* 查找结点i的前向邻接结点*/int findforward(CostType costnn,NodeNumber i,NodeNumber cur) int j; for(j=cur+1;j0) cur=j;return j; return -1;/* 输出最短路径序列*/void outpath(NodeNumber pathk) int i; for(i=0;ik;i+)printf(%dt,pathi);void main() NodeNumber m,t;/调用creatgraph函数。 creatgraph(cost);/调用outgraph函数。 outgraph(cost);/调用FPath算法 FPath(cost,path); printf(输出使用向前递推算法后的最短路径:n);/输出最短成本路径。 outpath(path); /调用BPath算法。 BPath(cost,path); printf(n输出使用向后递推算法后的最短路径:n);/输出最短成本路径。 outpath(path); printf(n输入要查找邻接结点的编号:); scanf(%d,&t);/调用findforward函数. printf(结点%d 的前向邻接结点为: n,t); cur=findforward(cost,t,cur); /*找剩下的前向邻接结点*/ while(cur!=-1) printf(%dt,cur); cur=findforward(cost,t,cur);/调用findbackward函数.printf(n结点%d 的后向邻接结点为: n,t); cur=findbackward(cost,t,cur); /*找剩下的后向邻接结点*/ while(cur!=-1) printf(%dt,cur);cur=findbackward(cost,t,cur); /getch();printf(n);system(pause);请输入图的成本矩阵: 0 9 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0 4 2 1 0 0 0 0 0 0 0 0 0 2 7 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 11 8 0 0 0 0 0 0 0 0 0 0 0 0 6 5 0 0 0 0 0 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0 0 0 5 6 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0输出图的成本矩阵: 0 9 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0 4 2 1 0 0 0 0 0 0 0 0 0 2 7 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 11 8 0 0 0 0 0 0 0 0 0 0 0 0 6 5 0 0 0 0 0 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0 0 0 5 6 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0请输出选择Vi: 16 7 9 18 15 7 5 7 4 2 5-请输出决策Di: 1 6 5 7 7 9 9 9 11 11 11-输出使用向前递推算法后的最短路径:0 1 6 9 11请输出选择