学校超市选址课程设计报告

学校超市选址问题需求分析数据模型〔规律构造〕:带权有向图(权值计算:距离*频度)存储构造:typedefstruct{stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];intvexnum;//,arcnum;}MGraph;核心算法:Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)输入数据:各单位名称，距离，频度，单位个数．输出数据:所选单位名称．floyd间的最短距离/最小权值。n*narcs(i,jij单位的最短距离/tt概要设计G=(V,E,wV={v1,v2,vn}。k≤n，V的一个子集。对于Vvi、vj，考虑从vi到vj的中间结点都在vk中的全部路径，设是其中最短的，并设的路径长度vkvi到vjvivk，vkvj，这样便得到表达式。上述争论可以归纳为如下递归式：1ij开头流程图开头MainMain〔〕输入根本信息GreatMgraph〔Gh〕建立邻接矩阵的存储构造Floyd算法NYA[i][j]==INF,i!=ji到j不存在路Floyed〔Gh〕输出i->j的路径和路径长度输出超市的最正确地址：i完毕具体设计1，A[i][jA[i][1]+A[1][j]中较A[i][jA(1),k〔k〕[i][jik2短路径长度。当第n-1〔n-1〔n-〕[i][j]ijn-1A(n-1)[i][jij头文件和变量设定#include”stdafx.h”#include<string.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#include“malloc.h“#include<iostream.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;构造体的定义typedefstruct{Vextypevexs[MAXVEX][MAXVEX]; //单位名称〔顶点信息；intadj[MAXVEX][MAXVEX];边；intdis[MAXVEX][MAXVEX];intf[MAXVEX];

//单位之间的相通状况〔//单位间距离〔边的长度；//各单位去超市的频率；3intn;inte;}Mgraph;变量的输入voidCreatMgraph(Mgraph*G){

//顶点数和边数；inti,j,k;printf(“请输入单位个数:\n“);scanf(“%d“,&(G->n));printf(“请输入单位间的路径数:\n“);scanf(“%d“,&(G->e));printf(“请输入单位名称:\n“);for(i=0;i<G->n;i++){%d:\n“,i);scanf(“%s“,&G->vexs[i]);}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++){

//构造体的初始化；G->adj[i][j]=0;G->dis[i][j]=0;G->f[i]=0;}for(k=0;k<G->e;k++){printf(:i,j):\n“);scanf(“%d,%d“,&i,&j);//在距离上表达为无向；4printf(“请输入一样两个单位间的距离(格式：dis)：\n“);scanf(“%d“,&(G->dis[i][j]));G->adj[i][j]=1;G->adj[j][i]=1;G->dis[j][i]=G->dis[i][j];}for(k=0;k<G->n;k++){%d:\n“,k);scanf(“%d“,&(G->f[k]));}for(i=0;i<G->n;i++) //以距离和频率之积作为

for(j=0;j<G->n;j++){G->dis[i][j]*=G->f[i]; //最终权值非完全无向；if(G->adj[i][j]==0&&i!=j)G->dis[i][j]=INF;}}带权有向图求最短路径floyd算法voidFloyed(Mgraph*G) //floyd{intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];for(i=0;i<G->n;i++) //初始化A[][]和path[][]5数组for(j=0;j<G->n;j++) //置初值；{A[i][j]=G->dis[i][j];path[i][j]=-1;count[i]=0;}for(k=0;k<G->n;k++) //k{for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)if(A[i][j]>(A[i][k]+A[k][j])) //ijk路径更短{A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}:\n“);for(i=0;i<G->n;i++)for(j=0;j<G->n;j++){if(i!=j){printf(“\n”);printf(“%d->%d;”,i,j);if(A[i][j]==INF){if(i!=j)6printf(“不存在路径\n“);}else{printf(“路径长度为:%d”,A[i][j]);printf(“路径为:%d*”,i);pre=path[i][j];while(pre!=-1){printf(“%d\n”,pre);pre=path[pre][j];}printf(“%d”,j);}}}//以下为选择总体最优过程，然后确址；for(i=0;i<G->n;i++)for(j=0;j<G->n;j++){if(A[i][j]==INF)count[i]=0;elsecount[i]=1;}for(i=0;i<G->n;i++)if(count[i]){for(j=0;j<G->n;j++)7if(i!=j)A[i][i]+=A[j][i];}k=0;for(i=0;i<G->n;i++){if(count[i])if(A[k][k]>A[i][i])k=i;}printf(“超市的最正确地址为:“);printf(“%s\n”,G->vexs[k]);}主函数模块voidmain{Mgraph*Gh=NULL;Gh=(Mgraph*)malloc(sizeof(Mgraph));CreatMgraph(Gh);Floyed(Gh);system(“pause“);}调试分析此题目的关键点之一：有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图8distance*frequency；这样就使得图的建立轻而易举。此题目的关键点之二：floyd此题目的关键点之三：path0〔Path=