最短路径问题编程

云南大学数学与统计学实验教学中心实验报告第1页共8页云南大学数学与统计学实验教学中心实验报告课程名称：运筹学实验学期：2012~2013学年第二学期成绩：指导教师：葛瑜学生姓名：卢富毓学生学号：20101910072实验名称：最短路径问题编程实验要求：必做实验学时：2学时实验编号：06实验日期：2013/4/30完成日期：2013/5/10学院：数学与统计学院专业：信息与计算科学年级：2010级一、实验目的编程实现图论中最短路的问题。对Dijkstra算法有一定的理解和掌握。二、实验环境VS2010（C++）三、实验内容给定一个连通图，求出此图的最短路径。（P261例题10图10-18）四、实验过程A、将上面算法编写实现运行结果如下图：首先需要读Dijkstra算法有一个全面的了解。这样才能很容易的编写程序。手工做和用程序来做还是有一些不同的（这一点后面会谈到。）将上图中的节点以及权值代入程序a、初始化结果：云南大学数学与统计学实验教学中心实验报告第2页共8页输入的结果为红色字体b、初始化后的到结果：红框中得到的图的关系与课本例题中的一样！所以创建图形正确！c、最后得到的结果：云南大学数学与统计学实验教学中心实验报告第3页共8页9x9的矩阵中，每一行中蓝色表示的是v1到该点的最短路径包含的节点。1x9的矩阵中，每一个紫色数代表的是v1到该点的最短路径的权值和。由1x9图中的数字可以看出，v1到v8的最短路径权值和为12.v1到v8包含顶点为{v1,v2,v3,v5,v8}v1没有到v9的路径。得到的结果与课本中例题的结果一致。所以编写的程序正确。五、实验总结通过对求最短路径问题用Dijkstra算法来编写程序，感觉到Dijkstra算法用手解起来比用程序来解决容易！用程序来解决则需要将程序中的每一步想清楚。虽然两者的结果以及算法思想都是一样的。但是在编写程序的时候还是能发现两者的不同的（当然，这是我的个人感觉）。O(∩_∩)O~在编写中，可以感觉的出，最短路径和最小支撑树的有一些地方是相同的，只是在核心的算法上一个用的是Prim算法一个用的是Dijkstra算法。六、源代码源代码如下：#includeiostream#includestring#includeWindows.husingnamespacestd;#defineMax_vex100#defineM1000//SetTextC1是原来的颜色//SetTextC2是设置的输出输入颜色#defineSetTextC1SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE)#defineSetTextC2SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN)云南大学数学与统计学实验教学中心实验报告第4页共8页#defineSetTextC3SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN|FOREGROUND_BLUE)#defineSetTextC4SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED)#defineSetTextC5SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_BLUE)#defineSetTextC6SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE)#defineSetTextC7SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN)classArcll{public:doubleweight;//权重};classPrimArc{public:stringvex;doubleminiWeight;};classGraphics{//创建一个图的类private:intvexnum;//顶点数intarcnum;//边数stringvexs[Max_vex];//存储定点名称Arcllarcs[Max_vex][Max_vex];//边数public:voidCreateGraphics(Graphics&G);//创建一个图intLocateIndex(GraphicsG,stringv);//寻找下标voidDijkStra(GraphicsG);};//找到相应顶点的下标intGraphics::LocateIndex(GraphicsG,stringv){inti=0;for(i=0;iG.vexnum;i++){if(G.vexs[i].compare(v)==0){returni;}}return-1;}//创建一个有向图voidGraphics::CreateGraphics(Graphics&G){inti,j,k;stringVi,Vj;doublew;//权值SetTextC1;cout-------------------------创建有向图的存储-------------------------------endl;cout请输入顶点数:;SetTextC4;//设置颜色云南大学数学与统计学实验教学中心实验报告第5页共8页cinG.vexnum;SetTextC1;//设置颜色cout请输入图的边数:;SetTextC4;cinG.arcnum;SetTextC1;cout请输入顶点名:;SetTextC4;for(i=0;iG.vexnum;i++){//初始化顶点cinG.vexs[i];}SetTextC1;for(i=0;iG.vexnum;i++){//初始化边for(j=0;jG.vexnum;j++){G.arcs[i][j].weight=M;}}for(k=0;kG.arcnum;k++){cout请输入第k+1条边相连的顶点Vi，Vj以及权值weight:;SetTextC4;cinViVjw;SetTextC1;i=LocateIndex(G,Vi);j=LocateIndex(G,Vj);if(i==-1||j==-1){cout输入错误！请检查...endl;return;}G.arcs[i][j].weight=w;}coutendl;cout各顶点的关系：endl;SetTextC2;for(i=0;iG.vexnum;i++){if(i==0){cout\t\tG.vexs[i];}else{cout\tG.vexs[i];}}coutendl;SetTextC3;for(i=0;iG.vexnum;i++){//初始化边SetTextC2;cout\tG.vexs[i];SetTextC3;for(j=0;jG.vexnum;j++){if(G.arcs[i][j].weight==M){云南大学数学与统计学实验教学中心实验报告第6页共8页SetTextC6;cout\tM;SetTextC3;}else{cout\tG.arcs[i][j].weight;}}coutendl;}SetTextC1;coutendl有向图创建完毕！endl;}/*------------------dijkstra算法------------------*/voidGraphics::DijkStra(GraphicsG){boolP[Max_vex][Max_vex];//最短路径P[][]boolfinal[Max_vex];//控制变量doubleD[Max_vex];//最短路径P带权长度和D[]inti,j,v,w;doublemin;stringvex=G.vexs[0];cout-----------------------------v0到vi的最短路径-----------------------------endl;intv0=LocateIndex(G,vex);for(v=0;vG.vexnum;v++){//初始化final[v]=FALSE;D[v]=G.arcs[v0][v].weight;for(w=0;wG.vexnum;w++){P[v][w]=FALSE;}if(D[v]M){P[v][v0]=TRUE;P[v][v]=TRUE;}}D[v0]=0;final[v0]=TRUE;for(i=1;iG.vexnum;++i){min=M;for(w=0;wG.vexnum;++w){if(!final[w]){if(D[w]min){v=w;min=D[w];}}}final[v]=TRUE;云南大学数学与统计学实验教学中心实验报告第7页共8页for(w=0;wG.vexnum;++w){if(!final[w]&&(min+G.arcs[v][w].weightD[w])){D[w]=min+G.arcs[v][w].weight;for(j=0;jG.vexnum;++j){P[w][j]=P[v][j];P[w][w]=TRUE;}}}}SetTextC2;for(i=0;iG.vexnum;i++){if(i==0){cout\t\tG.vexs[i];}else{cout\tG.vexs[i];}}coutendl;SetTextC3;for(i=0;iG.vexnum;i++){SetTextC2;cout\tG.vexs[i];SetTextC3;for(j=0;jG.vexnum;j++){if(P[i][j]){cout\tTrue;}else{SetTextC6;cout\tFalse;SetTextC3;}}coutendl;}SetTextC1;cout\n---------------------------v0到vi的最小权值和为---------------------------endl;SetTextC2;for(i=0;iG.vexnum;i++){if(i==0){cout\t\tG.vexs[i];}else{cout\tG.vexs[i];}}coutendl;cout\tG.vexs[0];SetTextC5;for(j=0;jG.vexnum;j++){if(D[j]==M){cout\tM;}else{云南大学数学与统计学实验教学中心实验报告第8页共8页cout\tD[j];}}SetTextC1;coutendl;}/*------------------dijkstra算法------------------*/intmain(){GraphicsG;SetTextC7;cout//dijkstra算法endl;cout//顶点从v1开始en