下载文档原格式
floyd算法的实现Floyd算法的实现Floyd算法是一种用于求解图中最短路径的算法，它可以在任意两个顶点之间找出最短路径的长度。
本文将介绍Floyd算法的具体实现过程。
Floyd算法的基本思想是利用动态规划的思想，通过多次迭代更新路径长度来获得最优解。
算法的核心是一个二维矩阵，其中每个元素表示从一个顶点到另一个顶点的最短路径长度。
我们需要初始化这个二维矩阵。
假设图中有n个顶点，我们可以创建一个n×n的矩阵，其中矩阵的每个元素初始值为无穷大。
然后，我们需要将图中已知的边的权重填入矩阵相应的位置。
接下来，我们开始进行迭代更新。
对于每对顶点i和j，我们检查是否存在一个中间顶点k，使得从i到j的路径经过k比不经过k 的路径更短。
如果存在这样的中间顶点k，我们就更新路径长度为经过k的路径长度。
具体而言，对于每一对顶点i和j，我们检查路径长度矩阵中的元素，如果存在一个中间顶点k，使得路径长度矩阵中的元素i到k的路径长度加上k到j的路径长度小于当前路径长度矩阵中i到j的路径长度，我们就更新路径长度矩阵中的元素为更短的路径长度。
我们重复以上步骤n次，每次迭代都会更新路径长度矩阵中的元素。
最终，当所有的路径长度都被更新后，我们就可以得到从任意一个顶点到另一个顶点的最短路径长度。
在具体实现的过程中，我们可以使用一个辅助矩阵来记录路径上的中间顶点。
如果存在中间顶点k，使得路径长度矩阵中的元素i到k 的路径长度加上k到j的路径长度小于当前路径长度矩阵中i到j 的路径长度，我们可以将辅助矩阵中的元素更新为k，以便在最后得到最短路径时能够还原路径。
Floyd算法的时间复杂度为O(n^3)，其中n为顶点的个数。
虽然时间复杂度较高，但Floyd算法具有一定的实用性，特别适用于顶点数较小、边数较多的稠密图。
总结一下，Floyd算法是一种用于求解图中最短路径的算法，通过多次迭代更新路径长度来获得最优解。
它的基本思想是利用动态规划的思想，通过不断比较中间顶点的路径长度来更新最短路径。
题目: 基于Floyd算法的医院选址实现初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）以邻接表为存储结构,建立n个结点的无向图；（2）用Floyd算法实现医院选址；（3）运行程序。
2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等；（4）结束语；（5）参考文献。
时间安排：2007年7月2日－7日（第18周）7月2日查阅资料7月3日系统设计，数据结构设计，算法设计7月4日-5日编程并上机调试7月6日撰写报告7月7日验收程序，提交设计报告书。
指导教师签名： 2007年7月2日系主任（或责任教师）签名： 2007年7月2日基于Flyod算法的医院选址实现摘要：以最短距离为最优目标选址的定量技术颇多，其中，最优化规划法及图论方法是研究热点。
本设计中阐述了无向网络中选址问题的Flyod基本模型及其全部顶点间最短路径算法选址的原理，并通过实例探讨了医院选址算法的步骤及C++语言实现的全过程。
关键词：最优化规划，Flyod 算法，医院选址，图论 0．引言“数据结构”在计算机科学中是一门综合性的专业基础课。
“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
选址问题，是指为一个和几个服务设施在一定区域内选定它的位置，使某一指标达到最优解。
这类问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。
基于Floyd最短路径算法的教材中心选址问题作者：赵丽娜李慧来源：《中国教育技术装备》2014年第04期摘要针对日益多元化的教育装备，校区分散、规模庞大的高校必须考虑其购买、管理、维护成本，因此，装备中心的选址尤为重要。
依据Floyd算法，深入探讨装备中心的选址问题，并给出量化的计算结果，为教育装备的管理工作提供依据。
关键词教育装备；最短路径；Floyd算法中图分类号：G48 文献标识码：B文章编号：1671-489X（2014）04-0040-03以计算机和互联网为代表的现代科技迅猛发展，越来越多的具有高科技含量的装备在教育领域得到了广泛应用，使教育装备的分配、管理、保障、运输和更新等工作变得更加复杂。
这势必要求学校的管理人员不仅要定性、更要定量地研究教育装备的决策问题，否则将无法做出可行性决策，更不要提什么优化了。
同时，我国的社会发展阶段和经济发展水平共同决定了教育经费的数目是有限的，在保证日常教学和科研的前提下，如何尽可能地压缩管理成本是教育装备管理工作中面临的难题。
因此，本文以如何使教育装备在运输过程中的成本最低为切入点，提出教育装备中心选址的最优化问题，采用Floyd最短路径算法实现其求解，为教育装备的管理工作提供科学依据。
1 数学模型图论的产生和发展经历了200多年历史，1736年瑞士著名数学家欧拉（L.Euler）提出并解决了“哥尼斯堡七桥问题”，标志着图论的起源[1]。
随着现代生产和科学技术的迅猛发展，特别是计算机的出现和互联网的普及，使图论方法得以快速扩展，图论已成为现代数学科学中的一门引人注目的新兴学科，渗透到物理学、化学、电工学、管理学、控制论、信息论等诸多学科[2-3]。
最短路径的求取是图论中的一个典型问题。
所谓最短路径是指在指定网络中两点间的一条距离最小的路[4]。
在求解网络上任意节点间最短路径的方法中，学术界一致公认的较好的算法是Dijkstra和Floyd算法。
这两个方法的主要区别是：Dijkstra算法可以计算从图中某一点到其他各点的最短路径；Floyd算法主要用于计算图中所有点之间的最短路径。
数据结构算法应用--基于Floyd算法的医院选址问题求解陈志珍;陈燕;李桃迎
【期刊名称】《教育教学论坛》
【年(卷),期】2014(000)036
【摘要】本文阐述了数据结构中Floyd最短路径算法的原理，实例讨论了使离医院最远的村庄到医院的路程最短的医院选址问题，将地理信息抽象为数据结构中的图，采用Floyd算法，描述了医院选址问题的算法及其具体实现步骤，最后通过C语言实现邻接矩阵的存储结构和主要算法。
【总页数】2页(P280-281)
【作者】陈志珍;陈燕;李桃迎
【作者单位】大连海事大学，辽宁大连 116026;大连海事大学，辽宁大连116026;大连海事大学，辽宁大连 116026
【正文语种】中文
【中图分类】G642.41
【相关文献】
1.基于Floyd算法的消防站选址确定 [J], 赵宪雅
2.基于Floyd算法的消防站选址确定 [J], 赵宪雅
3.Floyd算法在中心小学选址上的应用 [J], 吴焕瑞;贾艳军
4.基于AHP和Floyd算法的农产品物流中心选址研究 [J], 赵晏林;李琴;文忠波;周真丙
5.Floyd算法在大学城商业区选址问题中的应用研究 [J], 徐妮
因版权原因，仅展示原文概要，查看原文内容请购买。
本科14组 许泽东，邹志翔，陈佳成选址问题及最佳巡视路线的数学模型摘 要本文解决的问题是缴费站、派出所选址和最佳巡视路线的确定。
合理设置缴费站，可以为居民缴费节省大量时间和精力。
派出所位置和数量的不同选择，会产生不同的建设成本和管理经费。
而最佳巡视路线的确立，可以让领导在最短时间内巡视完所有社区。
为解决以上问题，我们建立的三个最优化模型。
针对问题一，我们先用floyd 算法求出各社区间的最短路，然后用计算机枚举出所有选址方案。
对每一种选址方案都会产生一个平均距离S ，我们以此为指标对方案进行评估。
经过合理化推导，我们得出最优解11712S .=（百米），且此时应该在M,Q,W 三社区设置煤气缴费站。
针对问题二，我们在问题一求出的最短路基础上，建立了0-1线性规划模型。
然后借助matlab 软件求得最优解3=X （即应该设置3个派出所），并给出了各派出所管辖范围。
这样既满足了每个社区在3分钟内至少能得到一个派出所服务，也为派出所的建设管理节省了不少成本。
具体结果如下表3：构建了社区网络的完全图，然后考虑到最优哈密顿圈的求解极其困难，我们连续使用30次模拟退火的方法求得连接各社区的近似最优哈密顿圈。
其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。
最终得到近似最优解128，见表4。
接着，我们还对哈密顿圈划分方法进行了改进，求得近似最优解125（具体结果见表5）。
1.问题重述问题背景 社区已是现代都市的的基础，随着城市社会经济的飞速发展，社区与人们生活的联系越来越密切，人们需要在社区解决日常生活涉及的各种利益和需要，因而人们对社区社会生活服务提出更高的要求，而政府也希望能够更好的指导和管理城市社区，社区生活服务建设以及安全保障等问题便由此而生。
据某项调查显示，我国七成以上的家庭表示需要更多更好的社会化社区服务，其范围涉及食、住、行、工、学、医、娱、境、安等居民生活的各个方面。
基于Flyod 算法的医院选址实现摘要：以最短距离为最优目标选址的定量技术颇多，其中，最优化规划法及图论方法是研究热点。
本设计中阐述了无向网络中选址问题的Flyod 基本模型及其全部顶点间最短路径算法选址的原理，并通过实例探讨了医院选址算法的步骤及C++语言实现的全过程。
关键词：最优化规划，Flyod 算法，医院选址，图论 0．引言“数据结构”在计算机科学中是一门综合性的专业基础课。
“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
选址问题，是指为一个和几个服务设施在一定区域内选定它的位置，使某一指标达到最优解。
这类问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。
也可以是生产服务设施，如仓库，转运站等等。
可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究。
尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。
本课程设计为基于Flyod 算法的医院选址的实现，因此在把实际的问题简化为网络模型后，建立约束函数和最终目标函数，运用Flyod 算法求出最优解。
例如本次设计中医院选址关心的是如何找到一个社区建立医院使所有的社区到医院的路径之和最短，没有约束函数,目标函数则为1,2111min{,,},1,2,,nnnj i j i i i sum V V Vn j n =====∑∑∑ 。
1．需求分析1.1影响医院选址的因素 1.1.1空间距离由于建医院的主要目的是收治病人，方便病人就医，使病人能在最短的时间内到达医院接受医治，因此院方必需调查所在地区各大社区到医院的空间距离，即病人到医院的直接距离。
此距离受地理条件，城市建筑等社会因素的限制。
选址问题数学模型选址问题数学模型摘要本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。
通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。
对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题针对问题1：0-1规划的穷举法模型。
该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。
针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。
最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。
最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。
针对问题3：建立了双目标最优化模型。
首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8 、11 和12.5 ，三组巡视的总路程达到35.3 ，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2 。
课程设计任务书学生姓名：专业班级：软件工程1101 指导教师：工作单位：计算机科学与技术学院题目: 基于Floyd算法医院选址的实现初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：软件工程系实验室提供计算机及软件开发环境。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）以邻接表为存储结构,建立n个结点的无向图（2）用Floyd算法实现医院选址（3）演示结果2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。
时间安排： 2013年元月21日－25日（第21周）元月21日查阅资料元月22日系统设计，数据结构设计，算法设计元月23日-24日编程并上机调试，验收程序元月25日撰写报告、提交报告指导教师签名： 2013年元月21日系主任（或责任教师）签名： 2013年元月21日程序代码如下：#include <iostream>using namespace std;int INFTY=32767;//整型数据的范围是-23768~32767，此处用32767表示无穷template<class T> //“T”为模板形参class Graph //基类{public:virtual void Insert(int u,int v,T& w)=0;virtual void Remove(int u,int v)=0;virtual bool Exist(int u,int v)=0;virtual int Vertices()const {return n;}protected:int n,e; //n表示村庄的个数，e表示无向图的边数};template <class T>class MGraph:public Graph<T>//邻接矩阵存储图{public:MGraph(); //构造函数，建立无向图~MGraph(); //析构函数，释放运行工程中的开辟的空间void Build_Graph(); //构建无向图void Insert(int u,int v,T& w); /*假如村庄节点的函数，包括权值，和相邻村庄编号*/void Remove(int u,int v); /*当两个村庄之间不能直接连通时，u，v两个村庄之间的权值就是无穷*/bool Exist(int u,int v); /*判断是否存在u，v两个村庄，存在返回true，否则返回false*/void Floyd(T**&d,int**&path); //建立Floyd函数，实现医院选址int num;protected:T**a; //二维数组，表示两个村庄之间的权值T noEdge;};template <class T>void MGraph<T>::Build_Graph()//建图{cout<<"请输入顶点的个数："<<endl;int C_num;cin>>C_num;num=n=C_num;e=0;noEdge=INFTY;a=new T*[n];for(int k=0;k<n;k++){a[k]=new T [n]; //开辟n个T类型大小的空间for(int j=0;j<n;j++)a[k][j]=noEdge;a[k][k]=0;}cout<<"建立村庄编号为1--"<<C_num<<"的图"<<endl;for(int i=0;i!=C_num;i++)for(int j=i+1;j!=C_num;j++){int w;cout<<"请输入村庄"<<i+1<<"与村庄"<<j+1<<"之间的权值：";cin>>w;Insert(i,j,w); //向图中添加权值为W的边cout<<i<<"--->"<<j<<":"<<a[i][j]<<endl;}cout<<"******************************************************** *************"<<endl;cout<<"已建立村庄编号为1--"<<C_num<<"的图:"<<endl;cout<<"**********************************"<<endl;cout<<" \t\t";for(int b=1;b<=C_num;b++)//输出邻接矩阵{cout<<b<<"\t";}cout<<endl;}template <class T>MGraph<T>::MGraph(){Build_Graph();}template <class T>MGraph<T>::~MGraph(){for(int i=0;i<n;i++)delete[]a[i];delete[]a;}template <class T>bool MGraph<T>::Exist(int u,int v){if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false; return true;}template <class T>void MGraph<T>::Insert(int u,int v,T &w){a[u][v]=w;a[v][u]=w;e++;}template <class T>void MGraph<T>::Remove(int u,int v){a[u][v]=noEdge;e--;}template <class T>void MGraph<T>::Floyd(T**&d,int**&path)//所有顶点之间的最短路径{int i,j,k;d=new T*[n];path=new int*[n];for(i=0;i<n;i++){d[i]=new T[n];path[i]=new int[n];for(j=0;j<n;j++){d[i][j]=a[i][j];if(i!=j&& a[i][j]<INFTY)path[i][j]=i; else path[i][j]=-1;}}for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(d[i][k]+d[k][j]<a[i][j]){d[i][j]=d[i][k]+d[k][j];path[i][j]=path[k][j];}}int main(){MGraph<int> Hospital;int **d,**path;int i,j,n;n=Hospital.num;Hospital.Floyd(d,path);int *sum=new int[n];cout<<endl;for(i=0;i!=n;i++)//输出矩阵{cout<<i+1<<"\t\t";sum[i]=0;for(j=0;j!=n;j++){sum[i]+=d[i][j];cout<<d[i][j]<<"\t";}cout<<endl;}cout<<"******************************************************** *************"<<endl;int min=0;for(i=0;i!=n;i++){cout<<i+1<<"村庄："<<sum[i]<<endl;if(sum[min]>sum[i])//判断最短路径min=i;}cout<<"医院应在编号为"<<min+1<<"的村庄"<<endl;for(i=0;i<n;i++){delete[]d[i];delete[]path[i];}delete[]d;delete[]path;return 0;}。
基于Flyod 算法的医院选址实现摘要：以最短距离为最优目标选址的定量技术颇多，其中，最优化规划法及图论方法是研究热点。
本设计中阐述了无向网络中选址问题的Flyod 基本模型及其全部顶点间最短路径算法选址的原理，并通过实例探讨了医院选址算法的步骤及C++语言实现的全过程。
关键词：最优化规划，Flyod 算法，医院选址，图论 0．引言“数据结构”在计算机科学中是一门综合性的专业基础课。
“数据结构”的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
选址问题，是指为一个和几个服务设施在一定区域内选定它的位置，使某一指标达到最优解。
这类问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。
也可以是生产服务设施，如仓库，转运站等等。
可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究。
尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。
本课程设计为基于Flyod 算法的医院选址的实现，因此在把实际的问题简化为网络模型后，建立约束函数和最终目标函数，运用Flyod 算法求出最优解。
例如本次设计中医院选址关心的是如何找到一个社区建立医院使所有的社区到医院的路径之和最短，没有约束函数,目标函数则为1,2111min{,,},1,2,,nnnj i j i i i sum V V Vn j n =====∑∑∑ 。
1．需求分析1.1影响医院选址的因素 1.1.1空间距离由于建医院的主要目的是收治病人，方便病人就医，使病人能在最短的时间内到达医院接受医治，因此院方必需调查所在地区各大社区到医院的空间距离，即病人到医院的直接距离。
此距离受地理条件，城市建筑等社会因素的限制。
1.1.2时间距离必需考虑时间距离。
这是病人从发病点到医院所需的时间（最好有80%的病人能在一个小时内到达医院），它受城市交通状况影响较大。
在我国城市当前交通不发达的情况下，应十分重视时间距离。
近年来，某大城市新建几所大医院的地址，虽然环境安静，地形理想，离社区的空间距离不太长，道路也较好，但唯独交通不便，时间距离长，开诊后病人少，并未减轻其他医院的压力，可谓目前城市新建医院选址的教训。
1.1.3其他因素建院选址，除考虑上述要求外，还应做到：纳入城市规划，合理布局；环境安静，利于修养；地形理想，便于绿化；公用设施，尽量利用；地质合适，易防污染；运输方便，运费低廉等到，这些条件也应综合考虑。
2.数据结构设计为了使问题更加具体，更加形象，便于求解，设计了一张网络图如下：图中的每个节点表示一个社区，一共有42个社区，社区与社区之间的数字为社区之间的距离。
要求是要在这42个社区里面选择一个社区建立医院，使其余社区到医院的距离之和最短。
2.1自定义结构体struct Graph{int vexnum;long arcx[M_vexnum][M_arcnum];};其中vexnum为图中的顶点数，在本图中它的值为43（0号单元为用），arcx[M_vexnum][M_arcnum]用来表示任意两个节点之间的距离，初始化的时候把不同顶点间的距离都设为无穷大，相同顶点间的距离设为0。
2.2结点距离矩阵的初始化与赋值for(i=1;i<G.vexnum;i++)for(j=1;j<G.vexnum;j++){if(i==j)G.arcx[i][j]=0;elseG.arcx[i][j]=INFINITY;}在程序运行的时候再对它们赋值，对于上图对其上三角矩阵赋值为：G.arcx[1][2]=40; G.arcx[1][33]=60;G.arcx[1][34]=45;G.arcx[2][3]=35;G.arcx[2][7]=50;G.arcx[2][9]=62;G.arcx[3][10]=42;G.arcx[3][36]=50;G.arcx[4][5]=10;G.arcx[4][6]=30;G.arcx[4][29]=40;G.arcx[4][30]=70;G.arcx[5][6]=28;G.arcx[5][39]=85;G.arcx[5][40]=38;G.arcx[6][11]=32;G.arcx[6][40]=30;G.arcx[6][41]=48;G.arcx[7][10]=48;G.arcx[7][27]=70;G.arcx[8][14]=36;G.arcx[8][15]=38;G.arcx[8][28]=50;G.arcx[9][27]=40;G.arcx[9][31]=52;G.arcx[9][40]=28;G.arcx[10][12]=52;G.arcx[11][15]=56;G.arcx[11][25]=40;G.arcx[11][27]=48;G.arcx[12][13]=80;G.arcx[13][20]=68; G.arcx[13][27]=50;G.arcx[14][17]=56;G.arcx[14] [23]=50;G.arcx[15][18]=58;G.arcx[15] [25]=46;G.arcx[15][42]=28;G.arcx[16][18]=75;G.arcx[16] [21]=58;G.arcx[16][23]=65;G.arcx[17][23]=52;G.arcx[18][19]=22;G.arcx[18] [23]=45;G.arcx[18][25]=30;G.arcx[19][22]=72;G.arcx[19] [26]=28;G.arcx[20][22]=80;G.arcx[20] [24]=50;G.arcx[21][22]=45;G.arcx[24][26]=30;G.arcx[25][26]=18;G.arcx[26][27]=70;G.arcx[27][40]=32;G.arcx[28][29]=60;G.arcx[28] [42]=32;G.arcx[29][30]=62;G.arcx[30][39]=15;G.arcx[31][32]=50;G.arcx[32][31]=50; G.arcx[32][34]=25; G.arcx[32][35]= 98; G.arcx[32][38]=68;G.arcx[32][39]=62;G.arcx[33][36]=40;G.arcx[33][37]=38;]G.arcx[35][39]=102;G.arcx[37][38]=35;G.arcx[41][42]=26;因为是无向图，所以V ij＝V ji ，得到图完整的邻接矩阵，语句如下：for(i=1;i<G .vexnum;i++) for(j=1;j<i;j++) G .arcx[i][j]=G .arcx[j][i]; 3.算法设计图论中的最短路径算法包括指定的顶点之间的最短路径算法和全部顶点间的最短路径算法。
前者可用于运输的合理化决策分析，一般用迪杰斯特拉（Dijkstra ）算法实现,而后者很适合于选址合理的中心等,使总的路程最短,一般用弗洛伊德(Flyod)算法求解。
3.1 算法的基本思想全部顶点间最短路径算法具有代表性的是1962年有福劳德（Flyod ）提出的算法。
它的主要思想是从代表任意2个顶点i V 到j V 的距离带权邻接矩阵开始，每次插入一个顶点k V ，然后将i V 到j V 间的已知最短路径于插入顶点k V 作为中间顶点（一条路径中始点外和终点外的其他顶点）时可能产生的i V 到j V 路径距离比较，取较小值以得到新的距离矩阵。
如此循环迭代下去，依次构造出n 个矩阵D （1）,D （2）, D （3）…,D （n ），当所有的顶点均作为任意2个顶点i V 到j V 中间顶点时得到的最后带权邻接矩阵D 就反映了所以顶点对之间的最短距离信息，成为图G 的距离矩阵。
最后对G 中各行元素求和值并比较大小，决定单个或多个最佳的中心。
3.2 Flyod 算法构造距离矩阵的原理对一个有n 个顶点的图G ，将顶点用n 个整数（从1到n ）进行编号。
把G 的带权邻接矩阵W 作为距离矩阵的初值，即D （0）＝（d （0）ij ）n*n ＝W 。
第一步构造D （1）＝（d （1）ij ）n*n ，其中d ij ＝min ｛d （1）i1＋d （1）1j ｝是从i V 到j V 的允许到1V 作为中间点的路径中最短距离长度。
第二步构造D （2）＝（d （1）ij ）n*n ，其中d ij ＝min ｛d （2）ij ，d （2）i2＋d （2）2j ｝是从i V 到j V 的只 许以1V ，2V 作为中间点的路径最短长度。
第n 步构造D （n ）＝（d （n ）ij ），其中d ij ＝min ｛d （n ）ij ，d （n ）in ＋d （n ）nj ｝是从i V 到j V 的只允许以1V ，2V ，3V ，…，n V 作为中间点的所有路径中最短路的长度，即是从i V 到j V 中间可插入任何顶点的路径中最短路的长度，因此D 即是距离矩阵。
4 .程序实现4.1图的初始化for(i=1;i<G.vexnum;i++)for(j=1;j<G.vexnum;j++){if(i==j)G.arcx[i][j]=0;elseG.arcx[i][j]=INFINITY;}4.2任意两个顶点之间最短距离的计算计算任意两个顶点之间的最短距离的方法有很多，最基本的有迪杰斯特拉（Dijkstra）算法和弗洛伊德（Flyod）算法。
相比之下，Flyod算法比Dijkstra算法更容易理解，算法在一次运算中可以求出任意两个顶点之间的距离,并且它们的时间复杂度都是o(n3)。
以下代码是整个程序中最重要的部分，它将求解出图的距离矩阵。
for(v=1;v<G.vexnum;v++)for(w=1;w<G.vexnum;w++){D[v][w]=G.arcx[v][w];for(u=1;u<G.vexnum;u++)P[v][w][u]=FALSE;if(D[v][w]<INFINITY){P[v][w][u]=TRUE;P[v][w][w]=TRUE;}}for(u=1;u<G.vexnum;u++)for(v=1;v<G.vexnum;v++)for(w=1;w<G.vexnum;w++)if(D[v][u]+D[u][w]<D[v][w]){D[v][w]=D[v][u]+D[u][w];for(i=1;i<G.vexnum;i++)P[v][w][i]=P[v][u][i];}4.3确定医院地址的算法得到图的距离矩阵后，要想从中得到医院的地址。
