数据结构课程设计——医院选址问题

来源：百度知道 编辑：UC知道 时间：2024/06/09 22:51:15
问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度．现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短．设计一程序求解此问题．
基本要求：用邻接矩阵表示无向网，应显示所选中的村庄到各村庄的最短距离。注，村庄编号、权值可输入。该题需要求出所有顶点之间的最短路径，然后求出每行的和，选择和值最小的那一行，则该行的下标所对应的村庄即为所求。
要求：解题原理、详细算法步骤和求解过程（要求能画出求解示意图）、核心算法代码（需注释）及算法时间复杂度分析、总结。
最好能以实验报告形式发给我，联系邮箱：yxyx-39@163.com
不希望看到的答案只是单纯的源代码，在此先谢谢大家。

#include <dos.h>
#include <time.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 10000 //定义权值的最大值
#define MAX_NUM 20 //图的最大顶点数
enum BOOL {False,True};
typedef struct
{
int arcs[MAX_NUM][MAX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点和边数
}Graph;
void CreateGraph(Graph &); //生成图的邻接矩阵
void ShortestPath_Floyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);
//用弗洛依德算法求每对顶点之间的最短路径
void CreateRGraph(Graph &G); //生成随机图

void main()
{
Graph G; //采用邻接矩阵结构的图
int u,i;
BOOL P[MAX_NUM][MAX_NUM][MAX_NUM]; //存放每对顶点的最短路径
int D[MAX_NUM][MAX_NUM]; //存放每对顶点的最短路径的距离
do{ //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: 根据输入数据寻找最佳村庄\n");
printf("\t