编辑代码

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

#define VertexNum 100 //最大顶点数设为100
#define INFINITY 65535 //对角权重设为双字节无符号整数的最大值

//边结点
typedef int Vertex;
struct ENode{
    Vertex V1,V2;
    int Weight;
};
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;

//图结点
struct GNode{
    int Nv;
    int Ne;
    int G[VertexNum][VertexNum];
};
typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;

MGraph CreateGraph(int VertexNums);
void InsertEdge(MGraph Graph,Edge E);
MGraph BuildGraph();
void FindAnimal(MGraph G);
int FindMaxDist(int D[][VertexNum],Vertex i,int N);
bool Floyd(MGraph Graph,int D[][VertexNum],Vertex path[][VertexNum]);

bool Floyd(MGraph Graph,int D[][VertexNum],Vertex path[][VertexNum]){
    Vertex i,j,k;

    //初始化
    for(i = 0;i < Graph->Nv;i++){
        for(j = 0;j < Graph->Nv;j++){
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }
    }

    for(k = 0;k < Graph->Nv;k++){
        for(i = 0;i < Graph->Nv;i++){
            for(j = 0;j < Graph->Nv;j++){
                if(D[i][k] + D[k][j] < D[i][j]){
                    D[i][j] = D[i][k] + D[k][j];
                    //若发现赋值图
                    if(i == j && D[i][j] < 0){
                        //不能正确解决,返回错误标记
                        return false;
                    }
                }

                path[i][j] = k;
            }
        }
    }
    
    //算法执行完毕,返回正确标记
    return true;
}

int FindMaxDist(int D[][VertexNum],Vertex i,int N){
    int MaxDist;
    Vertex j;

    MaxDist = 0;
    //找出i到其他动物j的最长距离
    for(j = 0;j < N;j++){
        //排除对角元的元素,以防读到对角元时返回正无穷
        if(i != j && D[i][j] > MaxDist){
            MaxDist = D[i][j];
        }
    }

    return MaxDist;
}

void FindAnimal(MGraph Graph){
    int D[VertexNum][VertexNum],path[VertexNum][VertexNum],MaxDist,MinDist;
    Vertex Animal,i;

    //Floyd(Graph,D);
    bool result = Floyd(Graph,D,path);
    if(result){

    MinDist = INFINITY;
    for(i = 0;i < Graph->Nv;i++){
        MaxDist = FindMaxDist(D,i,Graph->Nv);
        //说明有i无法变出的动物
        if(MaxDist == INFINITY){
            printf("0\n");
            return;
        }
        //找到最长距离更小的动物
        if(MinDist > MaxDist){
            //更新距离
            MinDist = MaxDist;
            //记录编号
            Animal = i + 1;
        }
    }
}
    printf("最容易变的动物是:%d号,变为最难变的距离需:%d\n",Animal,MinDist);
    //printf("%d %d\n",Animal,MinDist);
}

MGraph BuildGraph(){
    MGraph Graph;
    Edge E;
    int Nv;
    printf("输入结点数:\n");
    scanf("%d",&Nv);
    Graph = CreateGraph(Nv);
    printf("输入边数:\n");
    scanf("%d",&Graph->Ne);
    if(Graph->Ne != 0){
        E = (Edge)malloc(sizeof(struct ENode));
        for(int i = 0;i < Graph->Ne;i++){
        printf("输入要插入边的两个顶点以及权重\n");
        scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
        
        //动物从下标1开始,矩阵下标默认从0开始
        E->V1--;
        E->V2--;

        InsertEdge(Graph,E);
    }
}

    return Graph;
}

void InsertEdge(MGraph Graph,Edge E){
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph CreateGraph(int VertexNums){
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNums;
    Graph->Ne = 0;

    for(int i = 0;i < Graph->Nv;i++){
        for(int j = 0;j < Graph->Nv;j++){
            Graph->G[i][j] = INFINITY;
        }
    }

    return Graph;
}

int main () {
   MGraph G = BuildGraph();
   FindAnimal(G);

   return 0;
}