案例6-1.6 哈利波特的考试 (25分)-Dijkstra or Floyd

 

 解题思路：

1、用Floyd算法求出每个顶点到其他顶点所需要的最短路径（或者对每个顶点，用dijkstra算法求得单源最短路径）

2、再从每个顶点到其他顶点选出最长路径（按行或按列分别求最大值）

3、再这些选出的最长路径中选出最短路径长度以及其编号输出

4、若图不连通，则输出0

解法一、Floyd

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MaxV 100+1
int G[MaxV][MaxV];
int visit[MaxV];
int Nv,Ne;
void Initial()
{
    scanf("%d %d",&Nv,&Ne);
    memset(G,INF,sizeof(G));
    int i;
    for(i=1;i<=Nv;i++)
    {
        G[i][i]=0;
    }
    for(i=0;i<Ne;i++)
    {
        int v1,v2,x;
        scanf("%d %d %d",&v1,&v2,&x);
        G[v1][v2]=x;
        G[v2][v1]=G[v1][v2];
    }
}
void Floyd()
{
    int i,j,k;
    for(k=1;k<=Nv;k++)
    {
        for(i=1;i<=Nv;i++)
        {
            for(j=1;j<=Nv;j++)
            {
                if(G[i][k]+G[k][j]<G[i][j])
                G[i][j]=G[i][k]+G[k][j];
            }
        }
    }
}
int FindMax(int v)
{
    int i;
    int max=0;
    for(i=1;i<=Nv;i++)
    {
        if(G[v][i]>max)
        {
            max=G[v][i];
        }
    }
    return max;
}
void FindMinAnimal()
{
    int i,j,min;
    int MIN=INF;
    for(i=1;i<=Nv;i++)
    {
        if(FindMax(i)==INF)
        break;
        else if(FindMax(i)<MIN)
        {
            MIN=FindMax(i);
            min=i;
        }    
    }
    if(i>Nv)
    printf("%d %d",min,MIN);
    else
    printf("0");
}
int main()
{
    Initial();
    Floyd();
    FindMinAnimal();
    return 0;
}

解法二、Dijkstra

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MaxV 100
int G[MaxV+1][MaxV+1];
int visit[MaxV+1];
int Nv,Ne;
void Initial() {
    scanf("%d %d",&Nv,&Ne);
    memset(G,INF,sizeof(G));
    int i;
    for(i=1; i<=Nv; i++) {
        G[i][i]=0;
    }
    int v1,v2,x;
    for(i=0; i<Ne; i++) {
        scanf("%d %d %d",&v1,&v2,&x);
        G[v1][v2]=x;
        G[v2][v1]=G[v1][v2];
    }
}
void Dijkstra(int v) {
    int i,j,w;
    visit[v]=1;
    for(j=1; j<=Nv; j++) {
        int MIN=INF;
        for(i=1; i<=Nv; i++) {
            if(!visit[i]&&G[v][i]<MIN) {
                MIN=G[v][i];
                w=i;
            }
        }
        visit[w]=1;
        for(i=1; i<=Nv; i++) {
            if(!visit[i]&&MIN+G[w][i]<G[v][i]) {
                G[v][i]=MIN+G[w][i];
            }
        }
    }

}
int main() {
    Initial();
    int i,j;
    for(i=1; i<=Nv; i++) {
        memset(visit,0,sizeof(visit));
        Dijkstra(i);
    }
    int tmp[Nv+1];
    int flag=0;
    for(i=1; i<=Nv; i++) {
        int Max=0;
        for(j=1; j<=Nv; j++) {
            if(G[j][i]>Max) {
                Max=G[j][i];
            }
        }
        if(Max==INF) {
            flag=1;
            break;
        } else
            tmp[i]=Max;
    }
    if(flag)
        printf("0");
    else {
        int MIN=1;
        for(i=1; i<=Nv; i++) {
            if(tmp[i]<tmp[MIN])
                MIN=i;
        }
        printf("%d %d",MIN,tmp[MIN]);
    }

    return 0;
}