学校超市选址问题课程设计.docx

1、学校超市选址问题课程设计数据结构课程设计报告设计题目：学校超市选址问题 专 业 班 级 学 生 学 号 指导教师 起止时间 年 学期 问题描述对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。 1、需求分析核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)存储结构: typedef struct string vexsMAX_VERTEX_SIZE; int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE; int vexnum;/ ,a

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

3、图，其边V=v1, v2, , vn。对于kn，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i和j求，或者说求矩阵流程图3、详细设置 第一步，让所有路径加上中间顶点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) /带权有向图求最短路径floyd算法 int AMAXVEXMAXVEX,pathMAXVEXMAXVEX; int i,j,k,pre; int countMAXVEX; for(i=0;in;i+) /初始化A和path数组 for(j=0;jn;j+) /置初值； Aij=G-disij; pathij=-1; coun

5、ti=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; else cout路径长度为:Aijn; cout路径为:i*; pre=pathij; while(pre!=-1) coutpren; pre=

6、pathprej; coutjendl; /以下为选择总体最优过程，然后确址； for(i=0;in;i+) for(j=0;jn;j+) if(Aij=INF) counti=0; else counti=1; for(i=0;in;i+) if(counti) for(j=0;jn;j+) if(i!=j)Aii+=Aji; k=0; for(i=0;in;i+) if(counti) if(AkkAii) k=i; cout超市的最佳地址为:vexskendl;4、调试分析测试数据：输入：单位个数4单位间的路径数6第0个单位名称a第1个单位名称b第2个单位名称c第3个单位名称d相通两单位

7、 之间的距离0,1 31,2 22,3 20,3 30,2 41,3 1第0个单位去超市的频率 1第1个单位去超市的频率 2第2个单位去超市的频率 4第3个单位去超市的频率 3输出：相通两单位之间的路径和他的长度结果：附加程序#include #include #include #include #include malloc.h#include #define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXVEX=100;typedef char

8、 Vextype; /为复杂的声明定义简单的别名typedef struct Vextype vexsMAXVEXMAXVEX; /单位名称（顶点信息）； int adjMAXVEXMAXVEX; /单位之间的相通情况（是否有边）； int disMAXVEXMAXVEX; /单位间距离（边的长度）； int fMAXVEX; /各单位去超市的频率； int n; /顶点数和边数； int e;Mgraph;void CreatMgraph(Mgraph *G) /实现的是以邻接矩阵存储图，并能将矩阵打印，同时实现了图的深度遍历 int i,j,k; printf(请输入单位个数:n); sc

9、anf(%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(请输入相通的两单位 (输入格式:i,j):n); scanf(%d,%d,&i,&j);/在距离上体现为无向； printf(请输入相同两个单位间的距

10、离(格式：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 Floyed(Mgraph *G) /带权有向图求最短路径floyd算法 int AMAXVEXMAXVE

11、X,pathMAXVEXMAXVEX; int i,j,k,pre; int countMAXVEX; for(i=0;in;i+) /初始化A和path数组 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+)

12、if(i!=j) cout ij; if(Aij=INF) if(i!=j) cout不存在路径nendl; else cout路径长度为: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; else counti=1; for(i=0;in;i+) if(counti) for(j=0;jn;j+) if(i!=j)Aii+=Aji; k=0; for(i=0;in;i+) if(counti) if(AkkAii) k=i; cout超市的最佳地址为:vexskendl;int main() Mgraph *Gh=NULL; Gh=(Mgraph *)malloc(sizeof(Mgraph); CreatMgraph(Gh); Floyed(Gh); system(pause);