转载

Floyd算法应用-医院选址问题

1) 问题描述

n 个村庄之间的交通图可以用有向网图来表示，图中边< v _i , v _j >上的权值表示从村庄 i 到村庄 j 的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？

2) 基本要求

(1) 建立模型，设计存储结构；

(2) 设计算法完成问题求解；

(3) 分析算法的时间复杂度。

3) 设计思想

医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。

设图 G =（ V ， E ），对任一顶点 k ，称 E ( k )=max{d( i , k )}（ i ∈ V ）为顶点 k 的偏心度。显然，偏心度最小的顶点即为图 G 的中心点。

如图3(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。

4)医院选址问题的算法用伪代码描述如下：

1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；

2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；

3．具有最小偏心度的顶点即为所求。

5)代码附录

  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             else 103                 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             else 143                 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         else 197             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 }