数据结构课程设计-超市选址问题

数据结构课程设计-超市选址问题

ID:47204821

大小:77.50 KB

页数:11页

时间:2019-08-26

数据结构课程设计-超市选址问题_第1页
数据结构课程设计-超市选址问题_第2页
数据结构课程设计-超市选址问题_第3页
数据结构课程设计-超市选址问题_第4页
数据结构课程设计-超市选址问题_第5页
资源描述:

《数据结构课程设计-超市选址问题》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、.数据结构课程设计报告设计题目:学校超市选址问题专业计算机科学与技术班级10计本2班学生朱冬学号10012138联系方式18056570381..年学期问题描述对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。请为超市选址,要求实现总体最优。1、需求分析核心问题:求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型(逻辑结构):带权有向图(权值计算:距离*频度)存储结构:typedefstruct{stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];i

2、ntvexnum;//,arcnum;}MGraph;核心算法:Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)输入数据:各单位名称,距离,频度,单位个数.输出数据:所选单位名称.总体思路: 如果超市是要选在某个单位,那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个,那么就得到n*n的一张表格,arcs(i,j)表示i单位到j单位的最短距离/最小权值,这张表格中和最小的那一行(假设为第t行),那么超市选在t单位处就是最优解。运行环境DEV-C++2、概要设计 Floyd算法利用动态规划思想,通过把问题分解为子问题来解决任意两点见的最短路径问

3、题。设G=(V,E,w)是一个带权有向图,其边V={v1,v2,…,vn}。对于k≤n,考虑其结点V的一个子集。对于V中任何两个结点vi、vj,考虑从vi到vj的中间结点都在vk中的所有路径,设是其中最短的,并设的路径长度为。如果结点vk不在从vi到vj的最短路径上,则;反之则可以把分为两段,其中一段从vi到vk,另一段从vk到vj,这样便得到表达式。上述讨论可以归纳为如下递归式:..  原问题转化为对每个i和j求,或者说求矩阵开始流程图Main()输入基本信息GreatMgraph(Gh)建立邻接矩阵的存储结构Floyd算法NYA[i][j]==INF,i!=ji到j不存

4、在路径Floyed(Gh)输出i->j的路径和路径长度输出超市的最佳地址:i结束3、详细设置..第一步,让所有路径加上中间顶点1,取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值,完成后得到A(1),如此进行下去,当第k步完成后,A(k)[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后,得到A(n-1),A(n-1)即所求结果。A(n-1)[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度,即A(n-1)[i][j]表示从i到j的最短路径长度。代码表示如下:voi

5、dFloyed(Mgraph*G)//带权有向图求最短路径floyd算法{intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];for(i=0;in;i++)//初始化A[][]和path[][]数组for(j=0;jn;j++)//置初值;{A[i][j]=G->dis[i][j];path[i][j]=-1;count[i]=0;}for(k=0;kn;k++)//k代表运算步骤{for(i=0;in;i++)for(j=0;jn;j++)i

6、f(A[i][j]>(A[i][k]+A[k][j]))//从i经j到k的一条路径更短{A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}cout<n;i++)for(j=0;jn;j++){if(i!=j){cout<<""<"<

7、<n;i++)for(j=0;jn;j++){if(A[i][j]==INF)count[i]=0;elsecount[i]=1;}for(i=0;in;i++)if(count[i]){for(j=0;jn;j++)if(i!=j)A[i][i]+

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。