医院选址问题
发布网友
发布时间：2022-05-10 13:14
共2个回答
热心网友
时间：2023-10-10 01:01
#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("\t2: 随机生成村庄数与道路数进行测试\n");
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-2）
switch (i){
case 1: printf("首先输入村庄数目（2-19）和道路数目：\n例如：3,5\n");
printf("接着输入道路的起点和终点(i,j)及其路程。\n例如：\n1,2,4\n2,1,6\n1,3,11\n3,1,3\n2,3,2\n");
CreateGraph(G); //生成邻接矩阵结构的图
ShortestPath_Floyd(G,P,D); //利用弗洛依德算法求最短路径
break;
case 2: printf("随机产生的村庄数目与道路数目：");
CreateRGraph(G); //生成邻接矩阵结构的图
ShortestPath_Floyd(G,P,D); //利用弗洛依德算法求最短路径
break;
default: exit(1);
}
printf("\n");
}while(i!=0);
}
void CreateGraph(Graph &G)
{
//构造邻接矩阵结构的图G
int i,j,k;
int start,end,weight;
do{
printf("请输入村庄数目（2-19）和道路数目，格式：村庄数目，道路数目\n");
scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和边数
k=G.vexnum*(G.vexnum-1);
if(G.arcnum>k)
printf("error!!\n");
}while(G.arcnum<1||G.arcnum>k);
for(i=1;i<=G.vexnum;i++)
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=INFINITY; //初始化邻接矩阵
printf("请输入道路的起点和终点(i,j)及其路程，格式：起点，终点，路程：\n");
for(i=1;i<=G.arcnum;i++)
{scanf("%d,%d,%d",&start,&end,&weight); //输入边的起点和终点及权值
G.arcs[start][end]=weight;
}
}
void CreateRGraph(Graph &G)
{ //构造邻接矩阵结构的随机图G
int i,j;
int start,end,weight;
srand((unsigned)time(NULL));
G.vexnum=(rand()%(21-1))+1;
G.arcnum=(rand()%(G.vexnum*(G.vexnum-1)+1-1))+1;
printf("随机产生的医院数目与道路数目：%d,%d\n",G.vexnum,G.arcnum);//输出随机产生的医院与道路数目
for(i=1;i<=G.vexnum;i++)
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=INFINITY; //初始化邻接矩阵
for(i=1;i<=G.arcnum;i++)
{do{
start=(rand()%(G.vexnum+1-1))+1;
end=(rand()%(G.vexnum+1-1))+1;
weight=(rand()%(10000-1))+1;
}while((start==end)||(G.arcs[start][end]!=INFINITY));
printf("随机产生的第%d条道路起点，道路终点与距离：%d,%d,%d\n",i,start,end,weight);
G.arcs[start][end]=weight;}
}
void ShortestPath_Floyd(Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM])
{
//用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径P[v][w]
//及其带权路径长度D[v][w],
//若P[v][w][u]为True,表明u是从v到w当前求得最短路径上的顶点
int u,v,w,i,j,k,x;
int a[21]; //最短路径求和数组
for(v=1;v<=G.vexnum;v++) //各对顶点之间的初始已知路径及距离
for(w=1;w<=G.vexnum;w++)
{D[v][w]=G.arcs[v][w];
for(u=1;u<=G.vexnum;u++) P[v][w][u]=False;
if(D[v][w]<INFINITY) //从v到w有直接路径
{P[v][w][v]=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]&&v!=w) //从v经u到w的一条路径更短
{D[v][w]=D[v][u]+D[u][w];
for(i=1;i<=G.vexnum;i++)
if(P[v][u][i]||P[u][w][i]) P[v][w][i]=True;
}
}
printf("生成的最短路径的邻接矩阵为：\n");
for(v=1;v<=G.vexnum;v++)
{for(w=1;w<=G.vexnum;w++)
printf("%7d", D[v][w]);
printf("\n");}
printf("最短路径求和数组为：");
for(w=1;w<=G.vexnum;w++)
{{j=0;
for(v=1;v<=G.vexnum;v++)
j=j+D[v][w];
} //顶点到其它顶点最短距离的距离之和
a[w]=j;
printf("%7d",a[w]);}
printf("\n");
x=a[1];k=1;
for(w=1;w<=G.vexnum;w++)
{
if(a[w]<x)
{x=a[w];
k=w;}
}
printf("最适合建医院的村庄为：%d\n",k);
}
热心网友
时间：2023-10-10 01:02
