ddt.rar_ddt_动态规划多段图问题c语言_动态规划递推_多源点路径_实际路径规划

#include <iostream.h> #include <malloc.h> #include <conio.h> void main() { int num=1; int nodes,edges,i,j,r,k; int *D,*cost,*P;/*D是动态数组，COST数组存放代价，P数组是最小成本路径*/ typedef int **Value; Value value; cout<<" 开始演示程序"<<endl; cout<<"请输入结点数目:";cout<<endl<<"nodes=";/*输入图的结点数*/ cin>>nodes; cout<<"请输入边的数目:";cout<<endl<<"edges=";/*输入图的边数*/ cin>>edges; D=(int*)malloc(nodes*sizeof(int)); cost=(int*)malloc(nodes*sizeof(int)); P=(int*)malloc(nodes*sizeof(int)); value=(Value)malloc(nodes*sizeof(int*)); for(i=0;i<nodes;i++) { value[i]=(int*)malloc(nodes*sizeof(int)); } for(i=0;i<nodes;i++) for(j=0;j<nodes;j++) value[i][j]=-1; for(i=1;i<=edges;i++,num++) { cout<<"edge"<<num<<":"<<"from";/*输入图的路径*/ cin>>j; cout<<"to:"; cin>>k; cout<<"value="; cin>>value[j][k]; } cost[nodes]=0; for(j=nodes-1;j>=1;j--) { for(r=j+1;value[j][r]<0&&r<=nodes;r++); D[j]=r; k=value[j][r]+cost[r]; for(;r<=nodes;r++) if(value[j][r]>0) if(value[j][r]+cost[r]<k) { k=cost[j]=value[j][r]+cost[r]; D[j]=r; } } P[1]=1; for(j=2;P[j-1]<nodes;j++) { k=P[j-1]; P[j]=D[k]; } cout<<endl<<"最小成本路径:"<<endl;/*输出最小成本路径*/ for(i=1;i<=j-1;i++) cout<<P[i]<<"->"; char ch=getch(); }