7-6 选取医院建立的位置（C语言版详解）

设a、b、c、d、e、f表示一个乡的6个村庄,弧上的权值表 示两村之间的距离。现要在这6个村庄中选择一个村庄建一所医院,问医院建在哪个村庄 才能使离医院最远的村庄到医院的距离最短?

输入格式:

输入的第一行为村庄个数
输入的其他是多个存在组成网络的邻接矩阵表示

输出格式:

输出医院建立的位置

输入样例:

在这里给出一组输入。例如：

6
0 12 3 65535 9 10
12 0 65535 2 6 65535
3 65535 0 2 65535 6
65535 2 2 0 4 7
9 6 65535 4 0 4
10 65535 6 7 4 0

输出样例:

在这里给出相应的输出。例如：

c

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

解题思路：本体要求找到一个地点建医院，算出这个医院距离其它每个结点的最小距离，然后找到每个出发点这些最小距离中最远的那个作比较。找到最远距离最小的那个输出。

由于要用到最小路径，需要迪杰斯特拉算法

1.先对需要的东西进行定义

#define bool char
#define true 1
#define false 0
 
typedef char VerTexType; //字符型顶点数据类型
typedef int ArcType;     //边的权值类型为整型
#define MVNum 100        //最大顶点数
#define MaxInt 32767     //最大权值

2.图的结构，由于题中已经将邻接矩阵给出，所以不需要我们来自行创建 

//图的邻接矩阵存储表示
typedef struct
{
    VerTexType vexs[MVNum];    //顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;        //节点数和边数
}AMGraph;
 
//输入题中给的邻接矩阵
void Scanf(AMGraph* G, int n)
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            scanf("%d", &G->arcs[i][j]);
    G->vexnum = n;
}

3.迪杰斯特拉算法，其中D数组存放了起点v0到其他各个点位的最短距离，找到最大值返回。

算法简介：

1.初始化：

    （1）创建S数组存放结点被选中的情况，选过为True，没选为False；初始化时先全部置为False。

    （2）创建D数组存放到达从起点出发，到达其他顶点的距离，根据路径的发展，更小的权值会替换大的权值。初始化时先把出发点v0到其他结点的边赋给D。

    （3）创建Path数组存放每个结点的上一个结点（前置结点），通常用来遍历最短路径，本题虽然不需要用到，但还是写上了。 初始化时都置为-1代表没有边连接上一个。                   

    （4）开始时把出发点v0的S[v0]改为True代表选过了，起点到自己的距离D[v0] = 0;

2.找到各个最小路径

   （1）从第一个结点到最后一个结点都要找一次起点到它的最短路径，这是最外一层循环

   （2）在当前的D数组中找到最小权值的边，记录下来用以链接到该边连接的下一个结点 

   （3）把新选出结点的S数组置为True，并且将新结点带来的新路径（边）和之前的路径权值进行比较，比之前小就替换掉D数组中对应的值，再将新结点的前置结点设置为上一个结点。

3.返回每组中最远值    

int Dijkstra(AMGraph G, int v0)
{
    //S放是否选中过，D放起点距离其他点的距离，path放前驱结点，n是顶点个数
    int S[6], D[6], Path[6];
    int n = 6, i, w, v;
 
    //初始化
    for(v = 0; v < n; v++)
    {
        S[v] = false;    //先把S都置为未选中过
        D[v] = G.arcs[v0][v];   //把顶点距离其他结点的距离输入
        if(D[v] < MaxInt) Path[v] = v0;  //如果v0到v有边，那就把v的前置结点写上
        else Path[v] = -1;      //如果没边，就把前置结点设置为-1代表没有
    }
    S[v0] = true;  //起点设为选中过
    D[v0] = 0;     //起点到自己的距离为0
 
    //开始找最小距离
    int min;
    for(i = 1; i < n; i++)
    {
        min = MaxInt;
        for(w = 0; w < n; w++)
        {
            //没被选中 并且有边的 结点
            if(!S[w] && D[w] < min)
            {
                //就记录下结点的位置
                v = w;
                //并把它的权值暂存为最小权值
                min = D[w];
            }
        }
        //最小边的结点改为被选中
        S[v] = true;
        //从新选中的结点开始寻找，
        for(w = 0; w < n; w++)
        {
           //未被选中，并且从起始节点到目前能到达的结点的最小值
            if(!S[w] && D[v] + G.arcs[v][w] < D[w])
            {
                //总长度 = 之前长度的总和+到新结点的长度
                D[w] = D[v] + G.arcs[v][w];
                //新结点的前置结点设置
                Path[w] = v;
            }
        }
    }
    //找到每组最远的那个
    int max = 0;
    for(int s = 0; s < 6; s++)
    {
        if(max < D[s])
            max = D[s];
    }
 
    return max;
}

4.主函数，因为本体条件是固定的，所以很多地方的大小我便直接写了6。

int main()
{
    //输入
    AMGraph G;
    int n;
    scanf("%d",&n);
    Scanf(&G, n);
 
    int temp[6];
    int min = 0;
    //先把每组的最远距离搞出来
    for(int i = 0; i < 6; i++)
    {
        temp[i] = Dijkstra(G, i);
    }
    //找最远距离中最小的
    for(int i = 0; i < 6; i++)
    {
        if(temp[min]>temp[i])
            min = i;
    }
    //转换字符
    char name = (char)min+97;
    printf("%c",name);
 
 
    return 0;
}

 5.全部代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define bool char
#define true 1
#define false 0
 
typedef char VerTexType; //字符型顶点数据类型
typedef int ArcType;     //边的权值类型为整型
#define MVNum 100        //最大顶点数
#define MaxInt 32767     //最大权值
 
//辅助数组，用来记录从顶点集到
struct
{
    VerTexType adjvex;
    ArcType lowcost;
} closedge[MVNum];
 
//图的邻接矩阵存储表示
typedef struct
{
    VerTexType vexs[MVNum];    //顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;        //节点数和边数
}AMGraph;
 
//找到出发点得位置
int LocateVex(AMGraph* G, VerTexType v)
{
    for(int i = 0; i < G->vexnum; i++)
    {
        if(G->vexs[i] == v)
            return i;
    }
    return -1;
}
 
//输入题中给的邻接矩阵
void Scanf(AMGraph* G, int n)
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            scanf("%d", &G->arcs[i][j]);
    G->vexnum = n;
}
 
//测试用
void Print(AMGraph G)
{
    int i, j;
    for(i = 0; i < G.vexnum; i++)
    {
        for(j = 0; j < G.vexnum; j++)
            printf("%d ", G.arcs[i][j]);
        printf("\n");
    }
 
}
 
//从每个顶点出发，找最短路径
 
 
int Dijkstra(AMGraph G, int v0)
{
    //S放是否选中过，D放起点距离其他点的距离，path放前驱结点，n是顶点个数
    int S[6], D[6], Path[6];
    int n = 6, i, w, v;
 
    //初始化
    for(v = 0; v < n; v++)
    {
        S[v] = false;    //先把S都置为未选中过
        D[v] = G.arcs[v0][v];   //把顶点距离其他结点的距离输入
        if(D[v] < MaxInt) Path[v] = v0;  //如果v0到v有边，那就把v的前置结点写上
        else Path[v] = -1;      //如果没边，就把前置结点设置为-1代表没有
    }
    S[v0] = true;  //起点设为选中过
    D[v0] = 0;     //起点到自己的距离为0
 
    //开始找最小距离
    int min;
    for(i = 1; i < n; i++)
    {
        min = MaxInt;
        for(w = 0; w < n; w++)
        {
            //没被选中 并且有边的 结点
            if(!S[w] && D[w] < min)
            {
                //就记录下结点的位置
                v = w;
                //并把它的权值暂存为最小权值
                min = D[w];
            }
        }
        //最小边的结点改为被选中
        S[v] = true;
        //从新选中的结点开始寻找，
        for(w = 0; w < n; w++)
        {
           //未被选中，并且从起始节点到目前能到达的结点的最小值
            if(!S[w] && D[v] + G.arcs[v][w] < D[w])
            {
                //总长度 = 之前长度的总和+到新结点的长度
                D[w] = D[v] + G.arcs[v][w];
                //新结点的前置结点设置
                Path[w] = v;
            }
        }
    }
    //找到每组最远的那个
    int max = 0;
    for(int s = 0; s < 6; s++)
    {
        if(max < D[s])
            max = D[s];
    }
 
    return max;
}
 
 
 
 
int main()
{
    //输入
    AMGraph G;
    int n;
    scanf("%d",&n);
    Scanf(&G, n);
 
    int temp[6];
    int min = 0;
    //先把每组的最远距离搞出来
    for(int i = 0; i < 6; i++)
    {
        temp[i] = Dijkstra(G, i);
    }
    //找最远距离中最小的
    for(int i = 0; i < 6; i++)
    {
        if(temp[min]>temp[i])
            min = i;
    }
    //转换字符
    char name = (char)min+97;
    printf("%c",name);
 
 
    return 0;
}