《数据结构课程设计-超市选址问题》由会员分享，可在线阅读，更多相关《数据结构课程设计-超市选址问题（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计-超市选址问题数据结构课程设计报告设计题目：学校超市选址问题 专 业 计算机科学与技术 班 级 10计本2班 学 生 朱冬 学 号 10012138 联系方式 18056570381 年 学期问题描述对于某一学校超市,其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优. 1、需求分析核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型(逻辑结构）: 带权有向图 （权值计算: 距离频度）存储结构: typedef struct string vexsMAX_VERTEX_SIZE; int arcsMAX_VERTEX_
2、SIZEMAX_VERTEX_SIZE； int vexnum；/ ，arcnum；MGraph; 核心算法: Floyd算法(弗洛伊德算法每一对顶点之间的最短路径） 输入数据： 各单位名称，距离,频度，单位个数输出数据： 所选单位名称总体思路：如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。 假设顶点个数有n个，那么就得到nn的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行（假设为第t行),那么超市选在t单位处就是最优解。运行环境DEV-C+2、概要设计Floyd算法利用动态规划思想，通过把问题分解为子问题来
3、解决任意两点见的最短路径问题.设G=(V, E， w）是一个带权有向图，其边V=v1, v2， ， vn.对于kn，考虑其结点V的一个子集。对于V中任何两个结点vi、vj,考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的,并设的路径长度为。如果结点vk不在从vi到vj的最短路径上,则;反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i和j求，或者说求矩阵开始流程图Main（）输入基本信息GreatMgraph（Gh）建立邻接矩阵的存储结构Floyd算法NYAij=INF,i!=ji到j不存在路径Fl
4、oyed（Gh）输出i-j的路径和路径长度输出超市的最佳地址：i结束3、 详细设置 第一步，让所有路径加上中间顶点1,取Aij与Ai1+A1j中较小的值作Aij的新值，完成后得到A（1）,如此进行下去，当第k步完成后，A（k）ij表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n1步完成后,得到A（n1），A（n-1）即所求结果。A(n-1）ij表示从i到j且路径上的中点顶点的序号小于或等于n1的最短路径长度，即A(n1)ij表示从i到j的最短路径长度.代码表示如下：void Floyed(Mgraph *G） /带权有向图求最短路径floyd算法int AMAXVE
5、XMAXVEX，pathMAXVEXMAXVEX;int i,j，k，pre；int countMAXVEX;for(i=0;in；i+) /初始化A和path数组for（j=0;jG-n；j+） /置初值;Aij=G-disij；pathij=-1;counti=0;for（k=0；kG-n；k+） /k代表运算步骤for（i=0；iGn;i+）for（j=0；jGn;j+)if(Aij（Aik+Akj） /从i经j到k的一条路径更短Aij=Aik+Akj;pathij=k;coutendl”Floyed算法求解如下:endl;for(i=0；iG-n；i+)for（j=0；jGn;j+)i
6、f（i！=j）cout ”i”j;；if(Aij=INF）if（i！=j)cout不存在路径”n”endl；elsecout”路径长度为:”Aijn”;cout路径为：”i*;pre=pathij；while（pre!=1)coutpren”;pre=pathprej；coutjendl; /以下为选择总体最优过程，然后确址；for(i=0;in；i+)for(j=0；jn；j+）if(Aij=INF)counti=0;elsecounti=1;for(i=0；iGn;i+)if（counti)for(j=0;jn；j+)if(i！=j)Aii+=Aji; k=0;for(i=0;in;i+）
7、if(counti)if（AkkAii）k=i；cout”超市的最佳地址为：vexskinclude time。h#include malloc。h”#include e)）;printf（请输入单位名称:n”）；for(i=0;ivexsi）;for（i=0;iG-n;i+） /结构体的初始化；for（j=0;jfi=0;for(k=0；ke;k+）printf(请输入相通的两单位 (输入格式：i，j）:n”);scanf（d，d”，&i,&j）；/在距离上体现为无向;printf(”请输入相同两个单位间的距离(格式：dis)：n）;scanf（”d，&（Gdisij）);G-adjij=1；G-adjji=1;Gdisji=G-disij;for（k=0;kn；k+）printf(”请输入第%d个单位去超市的相对频率：n”,k);scanf（d,(Gfk)；for(i=0；iGn；i+) /以距离和频率之积作为权值；for（j=0;jdisij=INF;void Floyed（Mgraph G） /带权有向图求最短路径floyd算法int AMAXVEXMAXVEX，pathMAXVEXMAXVEX;int i，j，k，pre；int countMAXVEX；for(i=0;in；j+)
