1910072卢富毓插点问题

1、云南大学数学与统计学院 实 验 报 告课程名称：算法图论实验学期：20132014学年上学期成绩：指导教师：李建平姓名：卢富毓学号：20101910072实验名称：插值点问题实验要求：必做实验学时：2学时实验编号：02实验日期：2013-10-10完成日期：2013-10-21学院：数学与统计学院专业 ：信息与计算科学年级：2010级 一、实验目的利用dijskra算法实现路的插点问题，掌握如何寻找最短路集合的方法二、实验环境vs2010(c+)三、实验内容最短路的插点问题：给定一个连通赋权图g=（v,e;w.c;s.t）以及正整数d,这里w,c:e-r+s和t 是两个固定的顶点，找到s 到

2、t 的最短路集合构造一个新的辅助图，然后修改权值，再次调用dijskra算法寻求最短路。4、 实验过程a、插值算法具体描述如下：s和t 是两个固定的顶点，在图g中寻找一条从s到t的路ps,t，使得路ps,t的权重w(ps,t)不超过常数b，并向路ps,t的一些特殊边上插入一些顶点，不妨设得到的新路为p*s,t,使得新路中任意边的权重都不超过常数的d,目标是在满足上述条件情况下，求出插入顶点后所产生的费用达到最小.即实现,这里insert(e)表示加入到边e中新点的个数。dijskra算法即标号法，在上学期学过，这里就不作赘述。b、算法运行结果如下：/图的输入/图的创建以及插值点的限制/最后插值

3、点的结果五、实验总结通过编程，对寻找最短路径的dijkstra算法也体会更深；复习了求最短路的算法，思考了反圈算法在其中的一些应用。六、源代码#include#include#include#includeusing namespace std;#define max_vex 100#define m 1000/settextc1是原来的颜色/settextc2 是设置的输出输入颜色#define settextc1 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground

4、_red | foreground_green |foreground_blue)#define settextc2 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_green)#define settextc3 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_green | foreground_blue)#define sette

5、xtc4 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red)#define settextc5 setconsoletextattribute(getstdhandle(std_output_handle),foreground_intensity | foreground_red | foreground_blue)#define settextc6 setconsoletextattribute(getstdhandle(std_output_handl

6、e),foreground_red | foreground_green |foreground_blue)#define settextc7 setconsoletextattribute(getstdhandle(std_output_handle),foreground_green)double dmax_vex;/最短路径p带权长度和dbool pmax_vexmax_vex;/最短路径pstring vex,vex2;int v0,v1;class arcllpublic:double weight; /权重;class graphics /创建一个图的类private:int ve

7、xnum; /顶点数int arcnum; /边数string vexsmax_vex; /存储定点名称arcll arcsmax_vexmax_vex; /边数double d;/边的限制public:void creategraphics(graphics &g);/创建一个图int locateindex(graphics g, string v); / 寻找下标void dijkstra(graphics &g);void insertpoint(graphics &g);/找到相应顶点的下标int graphics:locateindex(graphics g, string v)i

8、nt i=0;for(i=0; ig.vexnum; i+)if(g.pare(v) = 0)return i;return -1;/创建一个图void graphics:creategraphics(graphics &g)int i,j,k;string vi,vj;double w; /权值settextc1;cout-创建有向图的存储-endl;coutg.vexnum;settextc1;/设置颜色coutg.arcnum;settextc1;cout请输入顶点名:;settextc4;for(i=0; ig.vexsi;settextc1;for(i=0; ig.

9、vexnum; i+) /初始化边for(j=0; jg.vexnum; j+)g.arcsij.weight = m;for(k=0; kg.arcnum; k+)cout请输入第k+1vivjw;settextc1;i = locateindex(g,vi);j = locateindex(g,vj);if(i = -1 | j = -1)cout输入错误！请检查.endl;return;g.arcsij.weight = w;g.arcsji.weight = w;coutendl;cout各顶点的关系：endl;settextc2;for(i=0; ig.vexnum; i+) if(

10、i=0)coutttg.vexsi ;else couttg.vexsi ;coutendl;settextc3;for(i=0; ig.vexnum; i+) /初始化边settextc2;couttg.vexsi ;settextc3;for(j=0; jg.vexnum; j+)if(g.arcsij.weight = m)settextc6;couttm ;settextc3; else couttg.arcsij.weight ;coutendl;settextc1;coutendl图创建完毕！endl;coutvex;coutendlvex2;coutendlg.d;/*-dijk

11、stra算法-*/void graphics:dijkstra(graphics &g)/bool pmax_vexmax_vex;/最短路径pbool finalmax_vex;/控制变量int i,j,v,w;double min;cout-v0到v1的最短路径-endl;v0 = locateindex(g,vex);v1 = locateindex(g,vex2);if(v0 = -1 | v1= -1)cout输入错误！请检查.endl;return;for(v = 0; v g.vexnum; v+ ) /初始化finalv = false;dv = g.arcsv0v.weigh

12、t;for(w = 0; w g.vexnum; w+)pvw = false;if(dv m)pvv0 = true;pvv = true;dv0 = 0;finalv0 = true;for(i = 1; i g.vexnum; +i)min = m;for(w = 0; w g.vexnum; +w)if(!finalw)if(dwmin)v = w;min = dw; finalv = true;for(w = 0; w g.vexnum; +w)if(!finalw & (min + g.arcsvw.weight dw)dw = min + g.arcsvw.weight;for(

13、j = 0; jg.vexnum; +j)pwj = pvj;pww = true;if(dv1=m)cout不连通！最短路不存在！endl;elsecout从g.vexsv0到g.vexsv1的最短路长度：;coutdv1endl;/*-路的插值算法-*/void graphics:insertpoint(graphics &g)int i,j;for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)if(i=j)continue;elseif(g.arcsij.weight+di=dj)g.arcsij.weight = ceil(g.arcsij.weight

14、/g.d)-1;elseg.arcsij.weight=m;coutendl;settextc2;for(i=0; ig.vexnum; i+) if(i=0)coutttg.vexsi ; else couttg.vexsi ;coutendl;for(i=0; ig.vexnum; i+)settextc2;couttg.vexsi ;settextc3;for(j=0; jg.vexnum; j+)if(g.arcsij.weight = m)if(g.arcsji.weight!= m)g.arcsij.weight = g.arcsji.weight;couttg.arcsij.weight ; else settextc6;couttm ;settextc3; else couttg.arcsij.weight ;coutendl;settextc6;g.dijkstra(g);/构造新的权值后，再寻找最短路cout最短路：;for(j=0;