center_point_by_floyd.c

#include <stdio.h>
#include <stdlib.h>

#define SIZE 6
#define INF 1000

void array_dump(int* array, int height, int width){
    int i = 0;
    int j = 0;

    for(i = 0; i < height; i++){
        for(j = 0; j < width; j++){
            printf("%d\t", array[i * height + j]);
        }
        printf("\n");
    }
}

void floyd(int* array, int size){
    int i, j, k;
    for(k = 0; k < SIZE; k++) {
        for(i = 0; i < SIZE; i++) {
            for(j = 0; j < SIZE; j++) {
                int m = array[i * size + j];
                int n = array[i * size + k] + array[k * size + j];
                array[i * size + j] = m < n ? m : n;
            }
        }
    }
}

int main(){
    int array[SIZE][SIZE] = {
        {0,20,15,INF,INF,INF},
        {2,0,INF,INF,10,30},
        {INF,4,0,INF,INF,10},
        {INF,INF,INF,0,INF,INF},
        {INF,INF,INF,15,0,INF},
        {INF,INF,INF,4,10,0}
    };

    // Dump old array
    array_dump((int *)array, SIZE, SIZE);
    printf("\n");

    // Call Floyd Algorithm
    floyd((int *)array, SIZE);

    // Dump shortest path
    array_dump((int *)array, SIZE, SIZE);
    printf("\n");

    // Calculate Eccentricity of This graph
    int eccentricity[SIZE] = {0};
    for (int i = 0; i < SIZE; ++i) {
        eccentricity[i] = 0;
        for (int j = 0; j < SIZE; j++) {
            // if(array[i][j] > eccentricity[i] && array[i][j] != INF){
            if(array[i][j] > eccentricity[i]){
                eccentricity[i] = array[i][j];
            }
        }
    }
    int min = INF;
    int index = -1;
    for (int i = 0; i < SIZE; ++i) {
        if (eccentricity[i] < min){
            min = eccentricity[i];
            index = i;
        }
    }
    printf("Eccentricity: %d\n", min);
    printf("Center Point: %d\n", index);

}