进阶实验6-3.2 社交网络图中结点的“重要性”计算 (30分)-Floyd或dijkstra算法

 

 解题思路：（邻接矩阵存储）

解法一、用Floyd算法算出每个顶点到其余顶点的最短路径

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MaxV 1001//取10001内存超限

int G[MaxV][MaxV];
int Nv,Ne;
void Initial() {
    int i,j;
    memset(G,INF,sizeof(G));
    int v1,v2;
    for(i=0; i<Ne; i++) {
        scanf("%d %d",&v1,&v2);
        G[v1][v2]=1;
        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 sum(int v) {
    int j;
    int sum=0;
    for(j=1; j<=Nv; j++) {
        if(v!=j)
            sum+=G[v][j];
    }
    return sum;
}
double Cal(int i) {
    return (Nv-1)/(double)(sum(i));
}
int main() {
    scanf("%d %d",&Nv,&Ne);
    int i;
    Initial();
    Floyd();
    int n,x;
    scanf("%d",&n);
    for(i=0; i<n; i++) {
        scanf("%d",&x);
        printf("Cc(%d)=%.2lf
",x,Cal(x));
    }

    return 0;
}

解法二、用dijkstra算法依次求出每个结点到其余结点的最短距离

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MaxVex 1000+10
int G[MaxVex][MaxVex];
int visit[MaxVex];
int Nv,Ne;
void Init() {
    memset(G,INF,sizeof(G));
    int i;
    for(i=1; i<=Nv; i++) {
        G[i][i]=0;
    }
    int v1,v2;
    for(i=0; i<Ne; i++) {
        scanf("%d %d",&v1,&v2);
        G[v1][v2]=1;
        G[v2][v1]=G[v1][v2];
    }
}
void Dijkstra(int s) {
    visit[s]=1;
    int i,j,w,MIN;
    for(j=1; j<=Nv; j++) {
        MIN=INF;
        for(i=1; i<=Nv; i++) {
            if(!visit[i]&&G[s][i]<MIN) {
                MIN=G[s][i];
                w=i;
            }
        }
        visit[w]=1;
        for(i=1; i<=Nv; i++) {
            if(!visit[i]&&MIN+G[w][i]<G[s][i]) {
                G[s][i]=MIN+G[w][i];
            }
        }
    }
}
int main() {
    scanf("%d %d",&Nv,&Ne);
    Init();
    int i,j;
    for(i=1; i<=Nv; i++) {
        memset(visit,0,sizeof(visit));
        Dijkstra(i);
    }
    int sum[MaxVex]={0};
    for(i=1; i<=Nv; i++) {
        for(j=1; j<=Nv; j++)
            sum[i]+=G[i][j];
    }
    int n,x;
    scanf("%d",&n);
    for(i=0; i<n; i++) {
        scanf("%d",&x);
        float tmp=(float)(Nv-1)/(float)sum[x];
        printf("Cc(%d)=%.2f
",x,tmp);
    }
    return 0;
}