数据结构算法应用——基于Floyd算法的医院选址问题求解

陈志珍，陈 燕，李桃迎

（大连海事大学，辽宁 大连 116026）

数据结构算法应用
——基于Floyd算法的医院选址问题求解

陈志珍，陈 燕，李桃迎

（大连海事大学，辽宁 大连 116026）

本文阐述了数据结构中Floyd最短路径算法的原理，实例讨论了使离医院最远的村庄到医院的路程最短的医院选址问题，将地理信息抽象为数据结构中的图，采用Floyd算法，描述了医院选址问题的算法及其具体实现步骤，最后通过C语言实现邻接矩阵的存储结构和主要算法。

数据结构；Floyd最短路径算法；医院选址；C语言

一、引言

《数据结构》课程是计算机类、信息管理类、电子商务、经济类及相关专业的一门重要的专业基础课程。早在1968年，美国一些学校的计算机系就开设《数据结构》课程。20世纪70年代中后期，我国也开设《数据结构》课程作为计算机专业的核心课程。开设该课程的目的在于让学者了解数据的计算机外部逻辑结构和计算机内部的存储结构以及相关操作，它为后续的专业课程，如编译原理、数据库原理、操作系统、系统分析与设计等课程提供必要的知识和技能准备。本人认为数据结构学习中的难点包括递归程序的阅读、非线性结构中图和树的相关算法，尤其是图的最短路径、拓扑排序、关键路径的基本应用，学习难点在于：图的存储结构、图中顶点的定位、图中各个顶点的访问方法等。本文试图就图的最短路径算法的学习过程进行探讨。在学习中，我们发现：在图形结构中，节点之间的关系可以是任意的，图中任意两个元素之间都有可能相邻，如果对图进行操作或者遍历的话，必须先确定图中第一个访问的顶点，才能对其他顶点进行访问（操作），因此，图是一种比线性表和树更为复杂的非线性数据结构。图之所以仍然作为《数据结构》课程的重要内容出现，是因为图的存储结构容易定义和掌握，但是需要通过图的形式化定义及其相关操作来实现具体问题的求解，这就是我们所说的在《数据结构》的图中需要掌握的重要知识点。图的运算已经成为人们解决实际问题的重要工具，比如通过Prim算法或Kruskal算法求最小生成树以构造最低价的通信网；通过关键路径求解确定一个工程中的“关键工程”；通过Dijkstra算法求某个源点到其余各个顶点的最短路径，解决物流配送的最短路径选择；通过Floyd算法计算每一对顶点之间的最短路径，用于确定设施的选址。本文重点讨论Floyd算法在医院选址问题中的应用。

医院是社会的重要基础设施，医院建设的选址必须本着以人为本、服务社会、经济效益的原则，如何使群众就医路径较短，是医院选址需要充分考虑的问题，本文以患者就医路径最短为切入点，选址问题转化为数据结构图论中的求解最短路径的问题，并采用Floyd算法对最短路径问题进行求解，为医院的选址问题提供定量分析。

二、Floyd算法基础概念

1.图：顶点和连线的集合，G=（V，VR），其中V是图中顶点的有穷非空集合，VR是两个顶点的关系的集合，即图中连线的集合。若VR中顶点对＜v，w＞是有序的，则为有向图，否则为无向图。

2.连通图：在无向图或者有向图G=（V，VR）中，若任意两个顶点v，w都能找到一条路径连接v和w，G即为连通图。

3.网：带权值的图称为网。

4.邻接矩阵：表示顶点之间连接关系的矩阵。网的邻接矩阵定义如下：

三、Floyd算法基本思想

最短路径问题是数据结构图论中的一个典型问题，这里的最短路径，不仅仅指的是距离的长短，还可以引申为经济费用、时间等广义上的最短。在数据结构中求解网络中任意两个顶点之间的最短路径的典型算法是Floyd算法。

Floyd算法的基本思想是：从带权邻接矩阵出发，若（vi，vj） 存在，则存在路径长度D[i][j]，但该路径不一定是最短路径，需要进行n次试探。如果存在一个k，且D[i][k]+D[k][j]＜D[i][j]，则将vk插入到vi到vj的路径中，得到新的矩阵D1，经过n次循环迭代，比较过所有顶点作为任意两个顶点之间的中间点的路径，得到最后的最短距离矩阵Dn。

四、实例应用

（一）医院选址问题建模

现假设给定n个村庄之间的交通图，现在要从这n个村庄中选择一个村庄建一所医院，要求离医院最远的村庄到医院的路程最短。

上述问题中，可将地理信息中的交通网络抽象为数学模型，以顶点表示村庄，以连线表示村庄之间的道路，因此交通图转化为由有限顶点和有限条边组成的无向图，图中顶点之间的关系由权值表示，定义权矩阵为前述网的带权邻接矩阵，wij的值为村庄之间的道路距离。这样医院选址问题就转化为在全部顶点之间最短距离的最大值中寻找最小值的问题，按照Floyd算法进行运算。

（二）医院选址算法示例

1.假设有6个村庄，村庄v0、v1之间道路距离为12，v0、v2为3，v0、v4为9，v0、v5为10，v1、v3为2，v1、v4为6，v2、v3为2，v2、v5为6，v3、v4为4，v3、v5为7，v4、v5为4。将6个村庄作为顶点，有直接道路的村庄之间连线，顶点之间的边所对应的权值为村庄之间的道路距离。

2.按照上文的算法，建立带权邻接矩阵D0。

3.第一次迭代，插入v0后计算最短路径，即两点之间可以有一个中间点的最短路径，D1[i][j]=min{D0[i][j]，D0[i] +D0[j]}。

4.第二次迭代，插入v1，D2[i][j]=min{D1[i][j]，D1[i]+D1[j]}，在D1的基础上构建D2。

5.第三次迭代，插入v2，D3[i][j]=min{D2[i][j]，D2[i]+D2[j]}，在D2的基础上构建D3。

6.第四次迭代，插入v3，D4[i][j]=min{D3[i][j]，D3[i]+D3[j]}，在D3的基础上构建D4。

7.第五次迭代，插入v4，D5[i][j]=min{D4[i][j]，D4[i]+D4[j]}，在D4的基础上构建D5。

8.第六次迭代，插入v5，D6[i][j]=min{D5[i][j]，D5[i]+D5[j]}，在D5的基础上构建D6，D6就是最后求得的最短距离矩阵。

9.以各个顶点为源点的最短距离的最大值maxdis= {9，9，6，7，9，9}，min{maxdis[i]}=6，对应顶点为v2，因此本例的最终医院选址为v2村庄。

（三）选址算法的C语言实现

1.图的邻接矩阵存储结构表示。

五、结论

实际应用中，医院选址问题需要考虑众多因素，可以设置权值为各项耗费总值。本文运用Floyd算法将医院选址问题进行了量化，并采用C语言实现，在实际的设施合理选择中，具有一定的理论意义和实用价值。除了选址问题，物流配送的路线选择、旅游中最短路线的设计等问题都可以通过建立数学模型进行算法设计。在数据结构的学习过程中，我们更需要学会的是如何将实际问题抽象为合理的数学模型，然后设计一个解决该模型的算法，最后进行编程、测试得到最终解答。

[1]陈燕,曹妍,贾红雨.数据结构（C语言版）[M].北京：科学出版社，2014．

[2]王军，王伟,公长春.基于多因素评价法下的社区医院投资研究[J].中国全科医学,2010，13（10A）：3143-3144.

[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2009.

[4]王晓东.算法设计与分析[M].北京：清华大学出版社,2011.

[5]赵丽娜，李慧.基于Floyd最短路径算法的教材中心选址问题[J].中国教育技术装备，2014，（4）：40-42.

G642.41

A

1674-9324（2014）36-0280-02

国家自然科学基金（71271034）；中央高校基本科研业务费（3132014307，3132014080）；辽宁省社科基金项目（L13DGL060）；辽宁省教育厅一般项目（L2012173）。

陈志珍（1992-），女，浙江衢州人，大连海事大学信息管理与信息系统专业本科生，研究方向：管理科学与决策支持系统；陈燕（1952-），女，辽宁大连人，博士，大连海事大学管理科学与工程教授，博士生导师，研究方向：交通运输现代化管理、决策支持系统、知识管理、数据仓库与数据挖掘；李桃迎（1981-），女，安徽萧县人，博士，大连海事大学管理科学与工程副教授，研究方向：决策支持、数据仓库与数据挖掘。