首页 > 代码库 > 医院选址问题【Floyd算法】
医院选址问题【Floyd算法】
1)问题描述
n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？
2) 基本要求
(1) 建立模型，设计存储结构；
(2) 设计算法完成问题求解；
(3) 分析算法的时间复杂度。
3) 设计思想
医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。
设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。
如图1.1所示是一个带权有向图，其各顶点的偏心度如图(b)所示。
医院选址问题的算法用伪代码描述如下：
1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；
2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；
3．具有最小偏心度的顶点即为所求。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define INFINITY 1000000 5 #define MAX_VERTEX_NUM 20 6 7 //定义弧的权值信息 8 typedef struct Arccell 9 { 10 int adj; //权值 11 } Arccell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //图的邻接矩阵 12 //定义结点信息 13 typedef struct VertexInfo 14 { 15 char name[20];//结点[村庄]名称 16 int position;//定点编号 17 } VertexInfo; 18 //图的结构 19 typedef struct Mgraph 20 { 21 VertexInfo vexs[MAX_VERTEX_NUM];//顶点数组 22 AdjMatrix arcs;//邻接矩阵 23 int vernum,arcnum;//分别指定顶点数和边数 24 } Mgraph; 25 26 27 //对图的初始化 28 Mgraph initgraph() 29 { 30 Mgraph c; 31 printf("请输入该图的顶点个数和弧的个数：\n"); 32 printf("顶点个数："); 33 scanf("%d",&c.vernum); 34 printf("弧的个数："); 35 scanf("%d",&c.arcnum); 36 //依次设置顶点编号 37 for(int i=0; i<c.vernum; i++) 38 { 39 c.vexs[i].position=i; 40 } 41 //依次输入各顶点信息 42 /* 43 strcpy(c.vexs[0].name,"a"); 44 strcpy(c.vexs[1].name,"b"); 45 strcpy(c.vexs[2].name,"c"); 46 strcpy(c.vexs[3].name,"d"); 47 strcpy(c.vexs[4].name,"e"); 48 49 */ 50 printf("\n请依次输入各个村庄的名称：\n"); 51 for(int i=0;i<c.vernum;i++) 52 { 53 printf("村庄%d:",i); 54 scanf("%s",&c.vexs[i].name); 55 56 } 57 58 //依次设置各弧的信息 59 for(int i=0; i<c.vernum; i++) 60 { 61 //先初始化邻接矩阵,相同点设置为0，其他全部设置为INFINITY（无穷大） 62 for(int j=0; j<c.vernum; j++) 63 { 64 c.arcs[i][j].adj=INFINITY; 65 if(i==j) 66 { 67 c.arcs[i][j].adj=0; 68 } 69 } 70 } 71 //再依次输入需要设置的权值 72 int i,j,k; 73 printf("请输入需要设置的弧长及其两端顶点[输入3个0结束]：\n"); 74 while(scanf("%d%d%d",&i,&j,&k)) 75 { 76 if(i==0&&j==0&k==0) 77 break; 78 c.arcs[i][j].adj=k; 79 } 80 /* 81 c.arcs[0][1].adj=1; 82 c.arcs[1][2].adj=2; 83 c.arcs[2][3].adj=2; 84 c.arcs[2][4].adj=4; 85 c.arcs[3][1].adj=1; 86 c.arcs[3][2].adj=3; 87 c.arcs[4][3].adj=5; 88 */ 89 return c; 90 } 91 92 //输出邻接矩阵 93 void printMatrix(Mgraph c) 94 { 95 printf("该图的邻接矩阵如下所示：\n"); 96 int count=0;//用于计数 97 for(int i=0; i<c.vernum; i++) 98 for(int j=0; j<c.vernum; j++) 99 {100 if(c.arcs[i][j].adj==INFINITY)101 printf(" #");102 else103 printf("%4d",c.arcs[i][j].adj);104 count++;105 if(count%c.vernum==0)106 printf("\n");107 }108 }109 110 void ShortestPath_Floyd(Mgraph G,int dis[][MAX_VERTEX_NUM])111 {112 //用floyd算法求有向网G中各对定点v和w之间的最短路径及其带权长度dis[v][w]113 for(int v=0; v<G.vernum; v++)114 for(int w=0; w<G.vernum; w++)115 {116 //对各结点之间初始化已知距离117 dis[v][w]=G.arcs[v][w].adj;118 }119 120 for(int u=0; u<G.vernum; u++)121 for(int v=0; v<G.vernum; v++)122 for(int w=0; w<G.vernum; w++)123 {124 if(dis[v][u]+dis[u][w]<dis[v][w])125 {126 //从v经u到w的路径更短127 dis[v][w]=dis[v][u]+dis[u][w];128 }129 }130 131 }132 //输出距离矩阵133 void printDis(Mgraph G,int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM])134 {135 printf("\n经过Flyod算法之后各顶点之间的距离如下：\n");136 for(int i=0; i<G.vernum; i++)137 {138 for(int j=0; j<G.vernum; j++)139 {140 if(dis[i][j]>=1000000)141 printf(" #");142 else143 printf("%4d",dis[i][j]);144 145 }146 printf("\n");147 }148 }149 150 //得到偏心度degree[]数组151 void getDegree(Mgraph G,int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM],int degree[])152 {153 for(int i=0;i<G.vernum;i++)154 {155 int max=dis[0][i];156 for(int j=0;j<G.vernum;j++)157 {158 if(dis[j][i]>max)159 max=dis[j][i];160 }161 degree[i]=max;162 }163 }164 165 166 167 int main()168 {169 printf("**********欢迎使用医院选址系统*********\n");170 Mgraph c=initgraph();171 system("cls");172 173 //输出邻接矩阵174 getchar();175 printMatrix(c);176 177 //定义距离数组，调用Floyd算法得到结果178 int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM];179 ShortestPath_Floyd(c,dis);180 181 //输出各个顶点之间的距离矩阵182 getchar();183 printDis(c,dis);184 185 //存放偏心度数186 int degree[c.vernum];187 getDegree(c,dis,degree);188 189 //显示各顶点的偏心度190 getchar();191 printf("\n各顶点的偏心度如下所示：\n");192 for(int i=0;i<c.vernum;i++)193 {194 if(degree[i]>=1000000)195 printf(" #\n");196 else197 printf("%4d\n",degree[i]);198 }199 200 //得到最小村庄的编号和名称201 int num;202 int min=degree[0];203 for(int i=0;i<c.vernum;i++)204 {205 if(min>degree[i])206 min=degree[i];207 }208 209 for(int i=0;i<c.vernum;i++)210 {211 if(min==degree[i])212 {213 num=i;214 break;215 }216 }217 getchar();218 printf("\n偏心度最小的村庄编号：%4d\n",num);//输出偏心度最小的村庄编号219 printf("医院应该建立在村庄: %4s \n",c.vexs[num].name);220 return 0;221 222 }
医院选址问题【Floyd算法】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。