最短路的插点问题

第1页共6页一、实验目的：寻找加细最短路，要求插点最少二、实验内容：1)题目：《运筹学》课本第282页的10.6。(1)其权重分布表如下：V1V2V3V4V5V6V7V8V9V1030400000V2003023000V3000000005V4000000300V5000003000V6000000102.5V7000000022V8000000004V90000000002)C语言代码：#includestdio.h#includemath.h#definem9/*定义结点个数*/#defined1/*任意边权重都不超过常数d*/floatM=1000000.0;/*用于比较权重选择最优路径*/floatB[m][m]={0.0},C[m][m]={0.0},gama[m]={0.0};/*记录权重*/intX[m]={0},Y[m]={0},E[m][m]={0};/*记录已选择的点*/intseta[m]={0};/*记录方向*/ints=0;floata=1.0;/*a为插点费用*/voidsearch(floatF[m][m])/*选择从所有已连点到未连点中权重最小但大于0的路径*/{floatM1=0.0;inti,j,k,k1=0,k2=0;M1=M;for(i=0;im;i++){第2页共6页if(X[i]==1){for(j=0;jm;j++){if(Y[j]==0){if(gama[i]+F[i][j]M1&&F[i][j]0){M1=gama[i]+F[i][j];k1=i;k2=j;}}}}}if(M1==M)s=1;else{for(k=0;km;k++)if(X[k]==1&&gama[k]+F[k][k2]==M1&&F[k][k2]!=0)C[k][k2]=(floor(C[k][k2]/d)-1)*a;elseC[k][k2]=0.0;seta[k2]=k1;gama[k2]=M1;X[k2]=1;Y[k2]=1;}}print()/*输出结果*/{inti,j;for(i=m-1;i0;){E[seta[i]][i]=1;i=seta[i];}for(i=0;im;i++)for(j=0;jm;j++)if(E[i][j]==1)printf(V%d——V%d,i+1,j+1);printf(\n从V1到V%d的总权重为：%f\n,m,gama[m-1]);}第3页共6页voidmain(){intflag=0;inti,j;printf(输入对应路径的权重：\n);for(i=0;im;i++)for(j=0;jm;j++){scanf(%f,&B[i][j]);C[i][j]=B[i][j];}X[0]=1;Y[0]=1;while(1){s=0;flag=0;search(B);if(s==1){if(X[m-1]==1){flag=1;break;}else{flag=2;break;}}}if(flag==1){printf(\n最短路为：\n);print();}elseprintf(\n没有从V1到V%d的路!\n,m);printf(\n新的权重矩阵为：\n);for(i=0;im;i++)for(j=0;jm;j++){第4页共6页E[i][j]=0;if(j==m-1)printf(%2.1f\n,C[i][j]);elseprintf(%2.2f,C[i][j]);}for(i=0;im;i++){gama[i]=0;X[i]=Y[i]=0;seta[i]=0;}X[0]=1;Y[0]=1;while(1){s=0;flag=0;search(C);if(s==1){if(X[m-1]==1){flag=1;break;}else{flag=2;break;}}}if(flag==1){printf(\n加细最短路为：\n);print();}elseprintf(\n加细最短路与最短路相同!\n,m);}3)运行结果：（1）第5页共6页（2）当d=3.0时，没有插点。三、使用环境适用于解决各种最短路的插点问题，在使用时需根据实际情况来更改预定义的m的值第6页共6页四、调试过程刚开始两次输出的路和权重相同，最后发现是定义的全局变量在再次调用search()函数时未改变，故输出相同结果。在第二个while循环之前重新将全局变量赋值五、总结缺点：只输出了一条最短路，没有输出全部最短路；