村庄建医院_最短路径，佛洛依德算法

处理的是在几个村庄之间建一个医院，使路径最短的问题，事实上也就是处理图中最短路径的问题，采用的是弗洛伊德算法

#include
 using namespace std;
 typedef struct
 {
	 double ** arc;
 }Graph;
 int MAX=999999999;//来表示无限大即无连接
 void creat（Graph &gint n）;//构造图
 void short_path（Graph &gint n）;//选择村庄
 int main（）
 {
	 int n;
	 cout<<“请输入顶点的个数：“;
	 cin>>n;
	 Graph g;
	 creat（gn）;
	 short_path（gn）;
	 return 0;
 }
 void creat（Graph &gint n）
 {
	 int ijk=0;
	 g.arc=new double *[n];//构造矩阵，用来存放各个村庄之间的直接距离
	 for（i=0;i		 g.arc[i]=new double[n];
	 for（i=0;i	 {
		 for（j=0;j			 g.arc[i][j]=MAX;
		 g.arc[i][i]=0;
	 }
	 cout<<“请输入每个顶点分别与其它顶点的关系，“<     cout<<“按位置、权值方式输入，以-1结束“<	 cout<<“每个关系只输入一遍“<	 cout<<“例如：共有3个村庄“<	 cout<<“1到2的距离为5.7，1到3的距离为4.5“<	 cout<<“2到3距离为7.5“<	 cout<<“当

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     110592  2008-05-29 12:02  图_村庄建医院\Debug\vc60.pdb

     文件     548974  2008-05-29 12:02  图_村庄建医院\Debug\图_村庄建医院.exe

     文件     262047  2008-05-29 12:02  图_村庄建医院\Debug\图_村庄建医院.obj

     文件    1106944  2008-05-29 12:02  图_村庄建医院\Debug\图_村庄建医院.pdb

     文件       2303  2008-05-14 18:34  图_村庄建医院\图_村庄建医院.cpp

     文件       3487  2008-05-29 12:02  图_村庄建医院\图_村庄建医院.dsp

     文件        534  2008-05-29 12:29  图_村庄建医院\图_村庄建医院.dsw

     文件      41984  2008-05-29 12:29  图_村庄建医院\图_村庄建医院.ncb

     文件      48640  2008-05-29 12:29  图_村庄建医院\图_村庄建医院.opt

     文件        896  2008-05-29 12:02  图_村庄建医院\图_村庄建医院.plg

     文件        526  2008-05-15 01:00  图_村庄建医院\操作说明.txt

     目录          0  2009-01-02 01:28  图_村庄建医院\Debug

     目录          0  2009-01-01 20:59  图_村庄建医院

----------- ---------  ---------- -----  ----

              2126927                    13