云南大学数学与统计学院 实 验 报 告课程名称：算法图论实验学期：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 到 t 的最短路集合构造一个新的辅助图，然后修改权值，再次调用dijskra算法寻求最短路。四、 实验过程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、算法运行结果如下：/图的输入/图的创建以及插值点的限制/最后插值点的结果五、实验总结通过编程，对寻找最短路径的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_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 SetTextC4 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_HANDLE),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 vexnum; /顶点数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)int i=0;for(i=0; iG.vexnum; i+)if(G.vexsi.compare(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.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(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;/*-dijkstra算法-*/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.weight;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