数据结构课程VC商店选址短路径Floyd算法实现含源代码

1、2008/2009学年度第二学期数据结构课程设计说明书题目:商店选址问题班级：姓名：学号：指导教师：日期：2009-6-222009-6-26计算机与信息工程系1、问题描述对于某一商店，其他各单位到其的距离不冋，冋时各单位人员去商店的频度也不冋。请为商店选址，要求实现总体最优。2、需求分析核心问题：求最短路径（选址的要求就是商店到各单位权值之和最少）数据模型（逻辑结构）：带权有向图（权值计算：距离*频度）存储结构：typedef structstri ng vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum

2、;/ ,arc num;MGraph;核心算法：Floyd算法（弗洛伊德算法-每一对顶点之间的最短路径）输入数据：各单位名称，距离，频度，单位个数.输出数据：所选单位名称.总体思路：如果商店是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个，那么就得到n*n的一张表格，arcs（i,j） 表示i单位到j单位的最短距 离/最小权值，这张表格中和最小的那一行（假设为第t行），那么商店选在t单位处就是最优解。3、开发环境1.硬件环境：PC兼容机2.软件环境：Visual C+ 6.03.操作系统：Win dows 20004、算法设计思想Floyd算法利用动

3、态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=（V, E, w）是一个带权有向图，其边V=v1, v2,vn。对于kDi,k+Dk,jThen Di,j:=Di,k+Dk,j;c) 算法结束：D即为所有点对的最短路径矩阵算法包括三个循环，每个循环需要运行步骤n,最内部的循环体可以在常数时间内完成，因此算法的复杂度为：0(nA3)。5、流程图6、课程设计过程中的关键算法Floyd算法表述：第一步，让所有路径加上中间顶点1，取Aij 与Ai1+A1j 中较小的值作Aij 的新值，完成后得到A(1),如此进行下去，当第k步完成后，A(k)ij 表示从i到就且路径上的中间顶点

4、的路 径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A(n-1)，A(n-1)即所求结果。A(n-1)ij 表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即A(n-1)ij表示从i到j的最短路径长度。代码表示如下：/void Floyed(Mgraph *G)int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;in t coun tMAXVEX;for(i=0;i n;i+)for(j=0;j n;j+)/带权有向图求最短路径floyd算法初始化A和path数组置初值；Aij=G-disij; pathij=-1

5、;coun ti=0;for(k=0;k n;k+)k代表运算步骤for(i=0;i n;i+)for(j=0;j n;j+)if(Aij(Aik+Akj)/从i经j到k的一条路径更短Aij=Aik+Akj;pathij=k;coutendlFloyed 算法求解如下:endl; for(i=0;i n;i+)for(j=0;j n;j+)if(i!=j)cout ij;if(Aij=INF)if(i!=j)cout不存在路径nendl; elsecout路径长度为：Aijn; cout路径为:i;pre=pathij;while(pre!=-1)coutpren; pre=pathprej;

6、coutje ndl;/以下为选择总体最优过程，然后确址；for(i=0;i n;i+)for(j=0;j n;j+)if(Aij=INF)coun ti=0;elsecoun ti=1;for(i=0;i n;i+)if(cou nti)for(j=0;j n;j+)Ai0+=Aij;for(i=0;i n;i+)k=0;if(cou nti)if(Ak0Ai0)k=i;cout商店的最佳地址为：vexskendl;7、测试及结果 测试数据：输入：单位个数、单位间的路径数、单位名称、相通两单位以及之间的距离、和各单位去商店 的频率输出：相通两单位之间的路径和他的长度结果：&总结与收获这次的程

7、序软件基本上运行成功，可以简单的对已经输入的数据进行计算，求出商店的最佳选址单位。但是程序较小，功能不全面，只是理论，并未实践。同时，这次数据结构课程设计让我们感触很深，使我们每个人都了解到的学习不应该只局限于我们的课本，因为课本上告诉我们的只是很有限的一部分，所涉及的面也是狭窄的。但是怎样在有 限的范围内学习到无限的知识呢？那就要我们自己懂得竞争，懂得自学，懂得充分利用身边的任何资源。应该说，我们在这次的课程设计中学到了很多知识，这并不仅仅包括书本上的知识，更重要 的是我们学会了如何去和别人交流，怎样用语言去实现自己的想法，在这个过程中使我懂得了勤学好问的重要性。虽然在我的程序中有一部分是从

8、网上搜索得来的，但我竭力将所获得的信息变成自己的资源。在我动手上机操作的同时，我在了解和看懂的基础上有所改变和创新，但是在我的程序软件中还有部分的不足，需要加以更新。同时，通过这次课程设计，我们都意识到了自己动手实践的弱势，特 别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。相信通过这次的课程设计，更让我深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这也是一笔很大的资源。在以后的时间中，我应该利用更多的时间去上机实验，多编写程序，相信不久后我的编程能力都会有很大的提高。经过这次课程设计，通过对程序的编制，调试 和运行，使我更好

9、的掌握了图基本性质和关于选址问题的解决方法，熟悉了各种调用的数据类型， 在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序 的设计中也有所体现。 课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。在整个课程程序中， 我们充分应用和调用各个程序模块，从而实现了此次程

10、序设计的所应该有的功能。在本组看来这就是我们在课程设计是比较成功的，而在这个过程中，让我们感觉收获最大 的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识（Floyd算法），充分的发挥了我们的主动性，使我们自主的去学习。9、参考文献1.马秋菊主编数据结构（C语言描述）北京：中国水利水电出版20062.严蔚敏吴伟民编者数据结构 （C语言版）北京：清华大学出版社20023.李春保苏光奎编者数据结构与算法教程北京：清华大学出版社20054.戴敏主编数据结构北京：机械工业出版社2000810、指导教师评语附件一：程序清单#include #include #include #include

11、malloc.h#include #define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767 const int MAXVEX=100;typedef char Vextype;typedef struct/Vextype vexsMAXVEXMAXVEX; int adjMAXVEXMAXVEX;单位名称（顶点信息）；/单位之间的相通情况（是否有边）int disMAXVEXMAXVEX;/ 单位间距离(边的长度);int fMAXVEX;/各单位去商店的频率;int

12、 n;/顶点数和边数；int e;Mgraph;void CreatMgraph(Mgraph *G)int i,j,k;printf(请输入单位个数:n);scanf(%d,&(G-n);printf(”请输入单位间的路径数：n);scanf(%d,&(G-e);printf(请输入单位名称:n);for(i=0;in;i+)printf(请输入第d个单位名称:n,i);scanf(%s,&G-vexsi);for(i=0;in;i+)/ 结构体的初始化；for(j=0;jn;j+)G-adjij=0;G-disij=0; G-fi=0;for(k=0;ke;k+)printf(请输入相通的

13、两单位(输入格式:i,j):n);scanf(%d,%d,&i,&j);在距离上体现为无向；printf(请输入相同两个单位间的距离(格式：dis) : n);scanf(%d,&(G-disij);G-adjij=1;G-adjji=1;G-disji=G-disij;for(k=0;kn;k+)printf(请输入第d个单位去商店的相对频率：n,k);scanf(%d，&(G-fk);for(i=0;in;i+)/以距离和频率之积作为权值;for(j=0;jn;j+)G-disij*=G-fi;/最终权值非完全无向；if(G-adjij=0&i!=j)G-disij=INF;void Fl

14、oyed(Mgraph *G)/带权有向图求最短路径floyd 算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;初始化A和path数组置初值；int countMAXVEX;for(i=0;in;i+)/for(j=0;jn;j+)/Aij=G-disij; pathij=-1;counti=0;for(k=0;kn;k+)k代表运算步骤for(i=0;in;i+)for(j=0;jn;j+)if(Aij(Aik+Akj) / 从 i 经 j 到 k 的一条路径更短 Aij=Aik+Akj;pathij=k;coutendlFloyed 算法求解如下 :endl;for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)cout ij;if(Aij=INF)if(i!=j)cout 不存在路径 nendl;elsecout 路径长度为 :Aijn;cout 路径为 :i ;pre=pathij;while(pre!=-1)coutpren;pre=pathprej;coutjendl;/ 以下为选择总体最优过程，然后确址；for(i=0;in;i+)for(j=0;jn;j+)if(