问题描述
在某个镇中包含n个村庄，现要从这n个村庄中选择一个村庄建立一所医院，这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近？（Floyd算法）
一堆废话
很久没有更新博客了，小白刚刚历经考试周的打击，百废待兴，赶紧跑来CSDN和小伙伴们取暖安慰受伤的心灵。近期会陆续写四篇数据结构课设的博客，然后再写两篇编写小游戏的博客，一个是基于Python的飞机大战，另一个是基于C++并在funcode上完成的海底世界游戏。
数据描述
（1）首先定义一个结构体，存放弧的权值信息。
#define Size 20
//定义弧的权值信息
typedef struct Arccell
{
int adj; //权值
} Arccell, AdjMatrix[Size][Size]; //图的邻接矩
（2）再定义一个结构体，存放村庄信息。
//定义结点信息
typedef struct VertexInfo
{
char name[20]; //结点[村庄]名称
int position; //定点编号
} VertexInfo;
（3）再定义一个图结构体，存放图的信息。
#define Size 20
//图的结构体
typedef struct Mgraph
{
VertexInfo vexs[Size];//顶点数组
AdjMatrix arcs;//邻接矩阵
int vernum,arcnum;//分别指定顶点数和边数
} Mgraph;
程序代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY 1000000
#define Size 20
//定义弧的权值信息
typedef struct Arccell
{
int adj; //权值
} Arccell, AdjMatrix[Size][Size]; //图的邻接矩阵
//定义结点信息
typedef struct VertexInfo
{
char name[20]; //结点[村庄]名称
int position; //定点编号
} VertexInfo;
//图的结构体
typedef struct Mgraph
{
VertexInfo vexs[Size];//顶点数组
AdjMatrix arcs;//邻接矩阵
int vernum,arcnum;//分别指定顶点数和边数
} Mgraph;
//对图的初始化
Mgraph InitGraph()
{
Mgraph c;
printf("请输入该图的顶点个数和弧的个数：\n");
printf("顶点个数：");
scanf("%d",&c.vernum);
printf("弧的个数：");
scanf("%d",&c.arcnum);
//依次设置顶点编号
for(int i=0; i<c.vernum; i++)
{
c.vexs[i].position=i;
}
printf("请依次输入各个村庄的名称：\n");
for(int i=0;i<c.vernum;i++)
{
printf("村庄%d\t",i);
scanf("%s",&c.vexs[i].name);
}
//依次设置各弧的信息
for(int i=0; i<c.vernum; i++)
{
//先初始化邻接矩阵,相同点设置为0，其他全部设置为INFINITY（无穷大）
for(int j=0; j<c.vernum; j++)
{
if(i==j)
c.arcs[i][j].adj=0;
c.arcs[i][j].adj=INFINITY;
}
}
//再依次输入需要设置的权值
int i,j,k;
printf("请输入两端顶点和弧长(输入3个0结束)：\n");
while(scanf("%d%d%d",&i,&j,&k))
{
if(i==0&&j==0&k==0)
break;
c.arcs[i][j].adj=k;
}
return c;
}
//输出邻接矩阵
void PrintMatrix(Mgraph c)
{
printf("该图的邻接矩阵如下所示：\n");
int count=0; //用于计数
for(int i=0; i<c.vernum; i++)
for(int j=0; j<c.vernum; j++)
{
if(c.arcs[i][j].adj==INFINITY)
printf(" #");
else
printf("%4d",c.arcs[i][j].adj);
count++;
if(count%c.vernum==0)
printf("\n");
}
}
//求最短路径
void ShortestPath_Floyd(Mgraph G,int dis[][Size])
{
//用floyd算法求有向网G中各对定点v和w之间的最短路径及其带权长度dis[v][w]
for(int v=0; v<G.vernum; v++)
for(int w=0; w<G.vernum; w++)
{
//对各结点之间初始化已知距离
dis[v][w]=G.arcs[v][w].adj;
}
for(int k=0; k<G.vernum; k++)
for(int i=0; i<G.vernum; i++)
for(int j=0; j<G.vernum; j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
{
//从v经u到w的路径更短
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
//输出距离矩阵
void PrintDis(Mgraph G,int dis[Size][Size])
{
printf("\n经过Flyod算法之后各顶点之间的距离如下：\n");
for(int i=0; i<G.vernum; i++)
{
for(int j=0; j<G.vernum; j++)
{
if(dis[i][j]>=1000000)
printf(" #");
else
printf("%4d",dis[i][j]);
}
printf("\n");
}
}
//求每个点最大路径
void GetDegree(Mgraph G,int dis[Size][Size],int degree[])
{
for(int i=0;i<G.vernum;i++)
{
int max=dis[0][i];
for(int j=0;j<G.vernum;j++)
{
if(dis[j][i]>max)
max=dis[j][i];
}
degree[i]=max;
}
}
int main()
{
printf("**********欢迎使用医院选址系统*********\n");
Mgraph c=InitGraph();
system("cls");
//输出邻接矩阵
PrintMatrix(c);
//定义距离数组，调用Floyd算法得到结果
int dis[Size][Size];
ShortestPath_Floyd(c,dis);
//输出各个顶点之间的距离矩阵
PrintDis(c,dis);
int degree[c.vernum];
GetDegree(c,dis,degree);
//得到最小村庄的编号和名称
int num;
int min=degree[0];
for(int i=0;i<c.vernum;i++)
{
if(min>degree[i])
min=degree[i];
}
for(int i=0;i<c.vernum;i++)
{
if(min==degree[i])
{
num=i;
break;
}
}
printf("医院应该建立在村庄: %4s \n",c.vexs[num].name);
return 0;
}
测试数据
（1）开始界面
（2）输入图的信息
（3）输出图的邻接矩阵
（4）输出图各顶点的距离矩阵
（5）输出建立医院的村庄名称