問題描述
在某個鎮中包含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）輸出建立醫院的村莊名稱