学校超市选址问题

数据结构课程设计报告PAGE3-数据结构课程设计报告题目：学校超市选址问题 目录 第1章需求分析 -2-第2章总体设计 -2-2.1文字描述 -2-2.2程序流程图 -2-第3章详细设计 -3-3.1数据结构 -3-3.2功能实现的算法及思路 -3-3.2.1建立图的邻接矩阵 -4-3.2.2迪杰斯特拉算法 -4-3.2.3确定最优地址 -4-第4章实现部分 -5-4.1核心代码 -5-第5章程序测试 -10-5.1测试数据 -10-5.2程序运行图 -11-5.3结果分析 -12-第6章总结 -12-参考文献 -12-第1章需求分析我的课程设计题目为学校超市选址问题。对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同，根据以上这两个条件，确定学校的超市要建在什么地方，才能使得方案达到最优。该程序要能够确定超市的最优地址。而这个最有地址只能在所有单位所在地中选择。通过这个课程设计，真正理解弗洛伊德算法的思想，锻炼自主学习能力和程序编写能力，以及能够处理现实生活中类似的问题。第2章总体设计2.1文字描述首先，建立图的邻接矩阵。输入相关基本数据信息，以单位作为图的顶点，以单位之间的距离与各个单位去超市的频率之积作为图的权值，建立邻接矩阵。然后，调用弗洛伊德算法。单位i与j之间，加入过渡点k，若i、k间距离与k、j间距离之和小于i、j间的距离，修改矩阵。如此反复执行下去。完成后，得到i到j得最短距离。最后，确定最优地点。根据某单位到各个单位的最短距离之和最短，该单位所在地即为最优地址。2.2程序流程图开始开始MMain()函数输入数据输入数据建立图的邻接矩阵建立图的邻接矩阵dijkstra算法dijkstra算法i!=j?i!=j?Y输出i->j的最短距离及路径输出i->j的最短距离及路径输出最优地址输出最优地址结束结束第3章详细设计数据结构定义一个Graph类来存储图的基本信息，代码如下：#definen4//定义顶点数#definee8//定义边数#define$32767//用$表示无穷大template<classT>classGraph{public: Graph(inta[][5]); voidvalue(intindex);//获得一个点到各个点的权值(提取dist数组中的数据) voidchoice();//计算路径之和选择最佳位置 voidprint(intindex);//打印路径 voidall_point();//多次调用迪杰斯特拉以实现求多源点路径的最小路径 voidshortest(intindex);//核心算法private: Tpath[n+1];//路径 intdist[n+1];//权值 Ts[n+1];//集合s保存已求出最短路径的顶点 intarcs[n+1][n+1];//邻接矩阵 Tv[n+1];//保存顶点 inttimes[n+1][n+1];//保存一个顶点到其他顶点的频度（也包括到自身的频度为0） intval[n+1][n+1];//保存一个顶点到其他顶点的权值(也包括到自身的距离为0)};3.2功能实现的算法及思路3.2.1建立图的邻接矩阵主要是通过多次调用迪杰斯特拉算法来完成对每个点求出最短路径。定义数组dist[n+1][n+1]存储单位间距离，数组times[n+1]存储各单位去超市的频率，数组arcs[n+1][n+1]表示单位间相通情况,数组path[n+1]保存路径,数组val[n+1]依次存储个点的dist数据。如果两单位i、j相通，则令arcs[i][j]=相应的权值，不相通则为$表示无穷大，自身到自身的权值为0。3.2.2迪杰斯特拉德算法首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为D[j]=Min{D|vi∈V}的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。迪杰斯特拉算法描述如下：1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[LocateVex(G,v),i]vi∈V2）选择vj，使得D[j]=Min{D|vi∈V-S}3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。3.2.3确定最优地址将数组a[i][j]中每行值之和放入每行的首地址中，即a[i][1]+=a[i][j]。然后比较每行首地址中的值。令k=1，若a[k][1]>a[i][1]，则将i赋给k.。如此循环n次。最后，输出unitname[k]，即为所求的地址。第4章实现部分实现代码/***********************************迪杰斯特拉算法 单源点最短路径 有向图利用邻接 矩阵进行存储************************************/#ifndef_DIJKSTRA_H_#define_DIJKSTRA_H_#definen4//定义顶点数#definee8//定义边数#define$32767//用$表示无穷大template<classT>classGraph{public: Graph(inta[][5]); voidvalue(intindex);//获得一个点到各个点的权值(提取dist数组中的数据) voidchoice();//计算路径之和选择最佳位置 voidprint(intindex);//打印路径 voidall_point();//多次调用迪杰斯特拉以实现求多源点路径的最小路径 voidshortest(intindex);//核心算法private: Tpath[n+1];//路径 intdist[n+1];//权值 Ts[n+1];//集合s保存已求出最短路径的顶点 intarcs[n+1][n+1];//邻接矩阵 Tv[n+1];//保存顶点 inttimes[n+1][n+1];//保存一个顶点到其他顶点的频度（也包括到自身的频度为0） intval[n+1][n+1];//保存一个顶点到其他顶点的权值(也包括到自身的距离为0)};#endif//dijkstra类的实现：#include<iostream>#include"dijkstra.h"usingnamespacestd;template<classT>Graph<T>::Graph(inta[][5]){ for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { arcs[i][j]=a[i][j];//赋值操作 val[i][j]=0; } } for(inti=1;i<=n;i++) { cout<<"请输入顶点："; cin>>v[i]; } for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { if(i!=j) { cout<<"请输入"<<v[i]<<"到"<<v[j]<<"的频度:"; cin>>times[i][j]; } else { times[i][j]=0;//自己到自己的频度为0； } } cout<<endl; } system("pause"); system("cls");}template<classT>voidGraph<T>::all_point()//多次调用算法获得路径{ for(inti=1;i<=n;i++) { shortest(i); print(i); value(i); }}template<classT>voidGraph<T>::shortest(intindex){ for(inti=1;i<=n;i++)//数据初始 { dist[i]=arcs[index][i]; s[i]=0; if((i!=index)&&(dist[i]<$)) { path[i]=v[index]; } else { path[i]=0; } } s[index]=v[index];//将源点并入S中 //dist[index]=0; for(inti=1;i<n;i++)//扫描一行获得权值 { intmin=$; intu=index; for(intj=1;j<=n;j++) { if((!s[j])&&(dist[j]<min)) { min=dist[j];//选取权值最小的路径 u=j;//并记录下该顶点号的位置 } } s[u]=v[u];//将求出的最短路径的顶点号并入S中 for(intw=1;w<=n;w++) { if((!s[w])&&(arcs[u][w]<$)&&(dist[u]+arcs[u][w]<dist[w]))//更新dist[]中的数据 { dist[w]=dist[u]+arcs[u][w];//权值更新 path[w]=v[u];//路径更新 } } } }template<classT>voidGraph<T>::print(intindex)//打印路径{ for(inti=1;i<=n;i++) { if(i!=index) { cout<<dist[i]<<":"; cout<<v[i];//输出终点 Tpre=path[i]; while(pre!=0) { cout<<"←"<<pre; pre=path[pre]; } cout<<endl; } } cout<<"********************************************"<<endl;}template<classT>voidGraph<T>::value(intindex)//获取权值{ for(inti=1;i<=n;i++) { val[index][i]=dist[i]; }}template<classT>voidGraph<T>::choice()//计算权值{ for(inti=1;i<=n;i++) { val[i][0]=0;//用零号单元保存路径之和,数据初始化 } /*for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { cout<<times[i][j]<<""; } cout<<endl; }*/ for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { val[i][0]+=(val[i][j]*times[i][j]);//开始计算权值与频度之积 } } intp=1;//记录最佳位置 intmin=val[1][0]; for(intk=1;k<=n;k++) { if(val[k][0]<min)//路径之和达到最小的即是最佳位置 { min=val[k][0]; p++; } cout<<v[k]<<"的路径之和为："<<val[k][0]<<endl; } cout<<"******************************************"<<endl; cout<<"******************************************"<<endl; cout<<endl<<""<<v[p]<<"的路径之和为："<<min<<"达到最小"<<endl; cout<<endl<<""<<"超市的位置选择在："<<v[p]<<"为最佳方案!"<<endl;}//main()函数引用部分/*该程序在vs2010旗舰版中顺利编译并且运行结果正确如果因为vc6.0编译环境下造成无法运行，则应修改代码中的循环变量，因为vc6.0对变量的作用域控制不够严谨导致程序无法运行。*****************************************************注意建立工程时应选择win32控制台，并且应对上述代码自行建立dijkstea.h，dijkstra.cpp和main.cpp三个工程文件*/#include<iostream>#include"dijkstra.cpp"intmain(){ /*inta[6][6]={-1,-1,-1,-1,-1,-1, -1,0,10,$,30,100, -1,