最短路的插点问题

1、一、实验目的：寻找加细最短路，要求插点最少二、实验内容：1) 题目：运筹学课本第282页的10.6。(1)其权重分布表如下：V1V2V3V4V5V6V7V8V9V1030400000V2003023000V3000000005V4000000300V5000003000V6000000102.5V7000000022V8000000004V90000000002)C语言代码：#include stdio.h#include math.h#define m 9 /*定义结点个数*/#define d 1 /*任意边权重都不超过常数d*/float M=.0; /*用于比较权重选择最优路径*/fl

2、oat Bmm=0.0,Cmm=0.0,gamam=0.0; /*记录权重*/int Xm=0,Ym=0,Emm=0; /*记录已选择的点*/int setam=0; /*记录方向*/int s=0;float a=1.0; /*a为插点费用*/ void search(float Fmm) /*选择从所有已连点到未连点中权重最小但大于0的路径*/ float M1=0.0; int i,j,k,k1=0,k2=0; M1=M; for(i=0;im;i+) if(Xi=1) for(j=0;jm;j+) if(Yj=0) if(gamai+Fij0) M1=gamai+Fij;k1=i;k2

3、=j; if(M1=M) s=1; else for(k=0;k0;) Esetaii=1;i=setai; for(i=0;im;i+) for(j=0;jV%d ,i+1,j+1); printf(n从V1到V%d的总权重为：%fn,m,gamam-1);void main() int flag=0; int i,j; printf(输入对应路径的权重：n); for(i=0;im;i+) for(j=0;jm;j+) scanf(%f,&Bij); Cij=Bij; X0=1;Y0=1; while(1) s=0; flag=0; search(B); if(s=1) if(Xm-1=1

4、) flag=1;break; else flag=2;break; if(flag=1) printf(n最短路为：n); print(); else printf(n没有从V1到V%d的路!n,m); printf(n新的权重矩阵为：n); for(i=0;im;i+) for(j=0;jm;j+) Eij=0; if(j=m-1) printf(%2.1fn,Cij); else printf(%2.2f ,Cij); for(i=0;im;i+) gamai=0;Xi=Yi=0;setai=0; X0=1; Y0=1; while(1) s=0; flag=0; search(C); if(s=1) if(Xm-1=1) flag=1;break; else flag=2;break; if(flag=1) printf(n加细最短路为：n); print(); else printf(n加细最短路与最短路相同!n,m);3)运行结果：（1）（2）当d=3.0时，没有插点。三、使用环境适用于解决各种最短路的插点问题，在使用时需根据实际情况来更改预定义的m的值四、调试过程刚开始两次输出的路和权重相同，最后发现是定义的全局变量在再