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

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

2、arcnum;MGraph;核心算法 : Floyd算法 ( 弗洛伊德算法 - 每一对顶点之间的最短路径)输入数据 :各单位名称，距离，频度，单位个数输出数据 :所选单位名称总体思路 :如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离 / 最小权值。假设顶点个数有距离 / 最小权值n 个，那么就得到n*n 的一张表格， arcs(i,j),这张表格中和最小的那一行( 假设为第t表示 i 单位到行 ) ，那么超市选在j 单位的最短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 算法NYAij=INF,i!=ji 到 j 不存在路Flo

4、yed（Gh ）输出 i->j 的路径和路径长度输出超市的最佳地址：i结束3、 详细设置第一步，让所有路径加上中间顶点1，取 Aij与 Ai1+A1j中较小的值作Aij的新值，完成后得到A(1), 如此进行下去，当第k 步完成后， A（ k）ij表示从 i 到就且路径上的中间顶点的路径的序号小于或等于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(Mgrap

5、h *G)/ 带权有向图求最短路径floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)/初始化 A 和/置初值；path数组Aij=G->disij;pathij=-1;counti=0;for(k=0;k<G->n;k+)/k代表运算步骤for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj)/ 从 i 经 j

6、到 k 的一条路径更短Aij=Aik+Akj;pathij=k;cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<" 不存在路径 "<<&quo

7、t;n"<<endl;elsecout<<" 路径长度为 :"<<Aij<<"n"cout<<" 路径为 :"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl;/ 以下为选择总体最优过程，然后确址； for(i=0;i<G->n;i+)for(j=

8、0;j<G->n;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;i<G->n;i+)if(counti)for(j=0;j<G->n;j+)if(i!=j)Aii+=Aji;k=0;for(i=0;i<G->n;i+)if(counti)if(Akk>Aii)k=i;cout<<" 超市的最佳地址为:"<<G->vexsk<<endl;4、调试分析测试数据：输入：单位个数4单位间的路径数6第 0 个单位名称a第 1 个单位名称b第 2 个

9、单位名称c第 3 个单位名称d相通两单位之间的距离0,131,222,320,330,241,31第 0 个单位去超市的频率1第 1 个单位去超市的频率2第 2 个单位去超市的频率4第 3 个单位去超市的频率3输出：相通两单位之间的路径和他的长度结果：附加程序#include <string.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#include "malloc.h"#include <iostream.h>#define TURE 1#de

10、fine FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXVEX=100;typedef char Vextype;typedef structVextype vexsMAXVEXMAXVEX;/ 单位名称（顶点信息） ；int adjMAXVEXMAXVEX;int disMAXVEXMAXVEX;int fMAXVEX;int n;/单位之间的相通情况（是否有边）/单位间距离（边的长度） ；/各单位去超市的频率；/顶点数和边数；int e;Mgraph;void Creat

11、Mgraph(Mgraph *G)int i,j,k;printf(" 请输入单位个数:n");scanf("%d",&(G->n);printf("请输入单位间的路径数:n");scanf("%d",&(G->e);printf(" 请输入单位名称 for(i=0;i<G->n;i+) :n");printf(" 请输入第 %d 个单位名称 scanf("%s",&G->vexsi);:n",i);f

12、or(i=0;i<G->n;i+)for(j=0;j<G->n;j+)/结构体的初始化；G->adjij=0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)printf(" 请输入相通的两单位(输入格式 :i,j):n");scanf("%d,%d",&i,&j);/在距离上体现为无向；printf(" 请输入相同两个单位间的距离(格式： dis)： n");scanf("%d",&(G->disij);

13、G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G->n;k+)printf(" 请输入第 %d 个单位去超市的相对频率:n",k);scanf("%d",&(G->fk);for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)/以距离和频率之积作为权值；G->disij*=G->fi;if(G->adjij=0&&i!=j)G->disij=INF;/ 最终权值非完全无向

14、；void Floyed(Mgraph *G)/ 带权有向图求最短路径floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)/ 初始化 Afor(j=0;j<G->n;j+)/置初值；和path数组Aij=G->disij;pathij=-1;counti=0;for(k=0;k<G->n;k+)/k代表运算步骤for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(

15、Aik+Akj)/ 从 i 经 j 到 k 的一条路径更短Aij=Aik+Akj;pathij=k;cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<" 不存在路径

16、"<<"n"<<endl;elsecout<<" 路径长度为 :"<<Aij<<"n"cout<<" 路径为 :"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl;/ 以下为选择总体最优过程，然后确址；for(i=0;i<G->n;i+) for(j=0;j<G->n;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;i<G->n;i+) if(counti)for(j=0;j<G->