【文件属性】：
文件名称：医院选址问题
文件大小：340KB
文件格式：DOC
更新时间：2015-01-26 04:24:58
医院选址问题，数据结构
医院选址问题
1. 问题描述
n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？
2. 基本要求
(1) 建立模型，设计存储结构；
(2) 设计算法完成问题求解；
(3) 分析算法的时间复杂度。
3. 设计思想
医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。
设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。
如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。
医院选址问题的算法用伪代码描述如下：
1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；
2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；
3．具有最小偏心度的顶点即为所求。
【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？
答：通过将图存储的方法很多，这儿用数组，简单化数据，可以更好的编号和运行程序。
